Code Logo

Longest Mod3 Balanced Subarray

Published at05 Jan 2026
Created by
Medium 13 views
Like13

Given an array of integers, find the length of the longest continuous subarray whose elements are balanced by their remainder when divided by 3. A subarray is balanced when it contains the same count of values from remainder group 0, group 1, and group 2.

You only need to return the length of that subarray, not the subarray itself. The three remainder counts inside the chosen window must all be equal.

For example, in [0,1,2,3,4,5], the whole array is balanced: 0 and 3 are in group 0, 1 and 4 in group 1, 2 and 5 in group 2 — two values per group — so the answer is 6. In [1,4,7,10], every value leaves remainder 1, so no balanced subarray exists and the answer is 0. In [3,6,9,2,5,8,1,4,7,12,15,18], the first nine entries contain three values from each remainder class, giving length 9.

A brute-force check of every subarray would take O(n^2) time. The efficient approach tracks a prefix state: as you scan, keep running counts of how many values from each remainder group have appeared. A subarray between two positions is balanced exactly when the differences between the group counts at those two positions are identical.

Edge cases include an empty array (return 0), an array where all values share the same remainder (return 0), and an array that is balanced only in a small inner window (return that window's length).

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

Solution Approach

Scan the array once while tracking running counts of values with remainder 0, 1, and 2. At each index, form a state key from the differences between those counts: (c0 - c1, c0 - c2). Store the first index where each state appeared in a hash map. When a state repeats, the stretch between its first appearance and the current index is balanced.

function longest_mod3_balanced_subarray(nums) {
  var map = { '0,0': -1 };
  var c0 = 0, c1 = 0, c2 = 0, maxLen = 0;
  for (var i = 0; i < nums.length; i++) {
    var r = ((nums[i] % 3) + 3) % 3;
    if (r === 0) c0++; else if (r === 1) c1++; else c2++;
    var key = (c0 - c1) + ',' + (c0 - c2);
    if (map[key] !== undefined) {
      var len = i - map[key];
      if (len > maxLen) maxLen = len;
    } else {
      map[key] = i;
    }
  }
  return maxLen;
}

Two positions have equal difference pairs exactly when the counts of each group increased by the same amount between them, which is the definition of a balanced window. Storing only the first occurrence of each state maximizes the window length for that state.

Time complexity is O(n), space complexity is O(n).

Best Answers

java
import java.util.*;

class Solution {
    public int longest_mod3_balanced_subarray(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;
    }
}