Code Logo

Longest Mod3 Balanced Subarray

Published at05 Jan 2026
Created by
Medium 2 views
Like13

This problem asks for the length of the longest continuous subarray where the numbers are balanced by their remainder when divided by 3.

Balanced means the subarray contains the same number of values from remainder group 0, remainder group 1, and remainder group 2. You are not returning the subarray itself here, only its length.

For example, in [0,1,2,3,4,5], the whole array is balanced because it has two values from each remainder group, so the answer is 6. In [1,4,7,10], every value has remainder 1, so there is no balanced subarray and the answer is 0.

So the job is to find the longest unbroken stretch where all three remainder groups appear equally often.

Example Input & Output

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
Recommendation Algorithm Flow for Longest Mod3 Balanced Subarray

Solution Approach

The clean trick is to use a prefix state instead of checking every subarray. As we scan the array, we keep counts of how many values have remainder 0, 1, and 2.

At each position, we store the difference pair:

(c1 - c0, c2 - c0)

If this same pair appears again later, it means the counts between those two positions changed by the same amount in all three groups. That is exactly what makes the subarray balanced.

So we remember the first index where each state appears. When we see that state again, we compute the current balanced length and update the best answer.

This turns the problem into a single pass with a hash map. The time complexity is O(n), and the extra space is O(n) for the stored states.

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;
    }
}