BudiBadu Logo

Longest Mod3 Balanced Subarray

Binary Search Medium 0 views
Like13

Longest Mod3 Balanced Subarray asks for the longest contiguous segment where counts of values with remainder 0, 1, and 2 (mod 3) are equal. Treat each number by its normalized remainder class, including correct handling for negative integers if present in extended cases.

The key observation is balance-state repetition. Track running counts for the three classes, then compress state into two differences such as (c0-c1, c0-c2). If the same pair appears again at a later index, the segment between those indices has equal increments across all three classes, hence balanced. Store the earliest index for each state and maximize length during traversal.

Judge covers already-balanced arrays, partial-balance cases, empty input, and arrays where no balanced segment exists. Return the maximum length integer only. Complexity is linear with map-backed state lookup. Correctness depends on initializing the zero-difference state at virtual index -1, which allows prefixes that are already balanced to be counted properly from the beginning of the array.

State keys should use normalized remainder classes and consistent difference ordering; changing the pair order mid-implementation will break lookups and lengths. Because only earliest occurrence matters for maximum span, never overwrite a state?s first index once recorded.

With this setup, each index is processed once and each state lookup is O(1), giving efficient behavior even for long telemetry streams.

Examples

Example 1
Input
nums = [3,6,9,2,5,8,1,4,7,12,15,18]
Output
9
Explanation

The first nine entries include exactly three readings from each remainder class.

Example 2
Input
nums = [1,4,7,10]
Output
0
Explanation

Every value leaves remainder one, so no balanced subarray exists.

Example 3
Input
nums = [0,1,2,3,4,5]
Output
6
Explanation

The entire array contains two values from each remainder class.

Algorithm Flow

Recommendation Algorithm Flow for Longest Mod3 Balanced Subarray - Budibadu
Recommendation Algorithm Flow for Longest Mod3 Balanced Subarray - Budibadu

Best Answers

java
import java.util.*;
class Solution {
    public int find_longest_mod3_balanced(int[] nums) {
        Map<String, Integer> map = new HashMap<>();
        map.put("0,0", -1);
        int maxLen = 0, c0 = 0, c1 = 0, c2 = 0;
        for (int i = 0; i < nums.length; i++) {
            int r = ((nums[i] % 3) + 3) % 3;
            if (r == 0) c0++;
            else if (r == 1) c1++;
            else c2++;
            String key = (c0 - c1) + "," + (c0 - c2);
            if (map.containsKey(key)) maxLen = Math.max(maxLen, i - map.get(key));
            else map.put(key, i);
        }
        return maxLen;
    }
}