Balanced Mod Subarrays

Published at05 Jan 2026

Like20

Each number belongs to one of three remainder groups based on num % 3. This problem asks you to return every maximal balanced subarray, where a balanced subarray has the same count of remainder 0, remainder 1, and remainder 2 values.

The word maximal matters here. You are not returning every balanced piece. You only return the longest ones that cannot be extended left or right without breaking the balance.

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

So the task is to find all continuous ranges where the three remainder groups are equally represented, then keep only the ranges that are maximal.

Example Input & Output

Example 1

Input

nums = [0,1,2,3,4,5]

Output

[[0,1,2,3,4,5]]

Explanation

The entire array has two values from each remainder class and is maximal.

Example 2

Input

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

Output

[[3,6,9,2,5,8,1,4,7],[2,5,8,1,4,7,12,15,18]]

Explanation

Two maximal balanced subarrays cover the timeline; neither can be extended without breaking the balance.

Example 3

Input

nums = [1,4,7,10]

Output

[]

Explanation

All values share the same remainder, so no balanced subarray exists.

Algorithm Flow

Recommendation Algorithm Flow for Balanced Mod Subarrays

Solution Approach

A useful trick here is to track how the remainder counts differ from each other as you move through the array. Let the running counts be c0, c1, and c2. A subarray is balanced when those counts increase by the same amount, which means the pair of differences stays the same at both ends.

One compact state is:

(c1 - c0, c2 - c0)

If the same state appears at two prefix positions, then the subarray between them is balanced.

So we scan the array, store the earliest and latest places where each state appears, and use those matches to recover balanced ranges. After that, we keep only the ones that are maximal instead of returning smaller balanced ranges sitting inside a larger one.

This approach avoids checking every possible subarray directly. With hashing on the prefix states, it runs in linear time relative to the array size, plus the work needed to build the final list of maximal ranges.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;

class Solution {
    public int[][] find_maximal_balanced_subarrays(int[] nums) {
        int p0 = 0, p1 = 0, p2 = 0;
        Map<String, List<Integer>> diffs = new HashMap<>();
        diffs.computeIfAbsent("0,0", k -> new ArrayList<>()).add(-1);
        
        for (int i = 0; i < nums.length; i++) {
            int r = (nums[i] % 3 + 3) % 3;
            if (r == 0) p0++;
            else if (r == 1) p1++;
            else p2++;
            String key = (p0 - p1) + "," + (p1 - p2);
            diffs.computeIfAbsent(key, k -> new ArrayList<>()).add(i);
        }
        
        List<int[]> balanced = new ArrayList<>();
        for (List<Integer> indices : diffs.values()) {
            for (int a = 0; a < indices.size(); a++) {
                for (int b = a + 1; b < indices.size(); b++) {
                    balanced.add(new int[]{indices.get(a) + 1, indices.get(b)});
                }
            }
        }
        
        List<int[]> maximal = new ArrayList<>();
        for (int[] b1 : balanced) {
            boolean isSub = false;
            for (int[] b2 : balanced) {
                if (b2[0] <= b1[0] && b2[1] >= b1[1] && (b2[0] != b1[0] || b2[1] != b1[1])) {
                    isSub = true;
                    break;
                }
            }
            if (!isSub) maximal.add(b1);
        }
        
        maximal.sort(Comparator.comparingInt(a -> a[0]));
        int[][] result = new int[maximal.size()][];
        for (int i = 0; i < maximal.size(); i++) {
            int start = maximal.get(i)[0];
            int end = maximal.get(i)[1];
            result[i] = Arrays.copyOfRange(nums, start, end + 1);
        }
        return result;
    }
}

javascript

function find_maximal_balanced_subarrays(nums) {
    let p = [0, 0, 0];
    let diffs = {"0,0": [-1]};
    for (let i = 0; i < nums.length; i++) {
        let r = (nums[i] % 3 + 3) % 3;
        p[r]++;
        let key = (p[0] - p[1]) + "," + (p[1] - p[2]);
        if (!diffs[key]) diffs[key] = [];
        diffs[key].push(i);
    }
    
    let balanced = [];
    for (let key in diffs) {
        let indices = diffs[key];
        for (let a = 0; a < indices.length; a++) {
            for (let b = a + 1; b < indices.length; b++) {
                balanced.push([indices[a] + 1, indices[b]]);
            }
        }
    }
    
    let maximal = [];
    for (let b1 of balanced) {
        let isSub = false;
        for (let b2 of balanced) {
            if (b2[0] <= b1[0] && b2[1] >= b1[1] && (b2[0] !== b1[0] || b2[1] !== b1[1])) {
                isSub = true;
                break;
            }
        }
        if (!isSub) maximal.push(b1);
    }
    
    maximal.sort((a, b) => a[0] - b[0]);
    return maximal.map(b => nums.slice(b[0], b[1] + 1));
}

php

function find_maximal_balanced_subarrays($nums) {
    $p0 = $p1 = $p2 = 0;
    $diffs = ["0,0" => [-1]];
    foreach ($nums as $i => $x) {
        $r = ($x % 3 + 3) % 3;
        if ($r == 0) $p0++;
        else if ($r == 1) $p1++;
        else $p2++;
        $key = ($p0 - $p1) . "," . ($p1 - $p2);
        $diffs[$key][] = $i;
    }
    
    $balanced = [];
    foreach ($diffs as $indices) {
        $count = count($indices);
        for ($a = 0; $a < $count; $a++) {
            for ($b = $a + 1; $b < $count; $b++) {
                $balanced[] = [$indices[$a] + 1, $indices[$b]];
            }
        }
    }
    
    $maximal = [];
    foreach ($balanced as $b1) {
        $isSub = false;
        foreach ($balanced as $b2) {
            if ($b2[0] <= $b1[0] && $b2[1] >= $b1[1] && ($b2[0] != $b1[0] || $b2[1] != $b1[1])) {
                $isSub = true;
                break;
            }
        }
        if (!$isSub) $maximal[] = $b1;
    }
    
    usort($maximal, function($a, $b) { return $a[0] - $b[0]; });
    
    $result = [];
    foreach ($maximal as $b) {
        $result[] = array_slice($nums, $b[0], $b[1] - $b[0] + 1);
    }
    return $result;
}

python

from typing import List

def find_maximal_balanced_subarrays(nums: List[int]) -> List[List[int]]:
    p0, p1, p2 = 0, 0, 0
    diffs = {(0, 0): [-1]}
    for i, x in enumerate(nums):
        r = (x % 3 + 3) % 3
        if r == 0: p0 += 1
        elif r == 1: p1 += 1
        else: p2 += 1
        d = (p0 - p1, p1 - p2)
        if d not in diffs: diffs[d] = []
        diffs[d].append(i)
    
    balanced = []
    for d, indices in diffs.items():
        if len(indices) < 2: continue
        for a in range(len(indices)):
            for b in range(a + 1, len(indices)):
                balanced.append((indices[a] + 1, indices[b]))
    
    if not balanced: return []
    
    maximal = []
    for i, j in balanced:
        is_sub = False
        for i2, j2 in balanced:
            if i2 <= i and j2 >= j and (i2 != i or j2 != j):
                is_sub = True
                break
        if not is_sub:
            maximal.append((i, j))
    
    maximal.sort()
    return [nums[i:j+1] for i, j in maximal]

rust

use std::collections::HashMap;

pub fn find_maximal_balanced_subarrays(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut p0 = 0;
    let mut p1 = 0;
    let mut p2 = 0;
    let mut diffs: HashMap<(i32, i32), Vec<i32>> = HashMap::new();
    diffs.insert((0, 0), vec![-1]);
    
    for (i, &x) in nums.iter().enumerate() {
        let r = (x % 3 + 3) % 3;
        if r == 0 { p0 += 1; }
        else if r == 1 { p1 += 1; }
        else { p2 += 1; }
        let d = (p0 - p1, p1 - p2);
        diffs.entry(d).or_insert(vec![]).push(i as i32);
    }
    
    let mut balanced = Vec::new();
    for indices in diffs.values() {
        if indices.len() < 2 { continue; }
        for a in 0..indices.len() {
            for b in a + 1..indices.len() {
                balanced.push((indices[a] + 1, indices[b]));
            }
        }
    }
    
    let mut maximal = Vec::new();
    for &(i, j) in &balanced {
        let mut is_sub = false;
        for &(i2, j2) in &balanced {
            if i2 <= i && j2 >= j && (i2 != i || j2 != j) {
                is_sub = true;
                break;
            }
        }
        if !is_sub {
            maximal.push((i, j));
        }
    }
    
    maximal.sort();
    maximal.into_iter().map(|(i, j)| {
        nums[i as usize ..= j as usize].to_vec()
    }).collect()
}

typescript

function find_maximal_balanced_subarrays(nums: number[]): number[][] {
    let p = [0, 0, 0];
    let diffs: {[key: string]: number[]} = {"0,0": [-1]};
    for (let i = 0; i < nums.length; i++) {
        let r = (nums[i] % 3 + 3) % 3;
        p[r]++;
        let key = (p[0] - p[1]) + "," + (p[1] - p[2]);
        if (!diffs[key]) diffs[key] = [];
        diffs[key].push(i);
    }
    
    let balanced: [number, number][] = [];
    for (let key in diffs) {
        let indices = diffs[key];
        for (let a = 0; a < indices.length; a++) {
            for (let b = a + 1; b < indices.length; b++) {
                balanced.push([indices[a] + 1, indices[b]]);
            }
        }
    }
    
    let maximal: [number, number][] = [];
    for (let b1 of balanced) {
        let isSub = false;
        for (let b2 of balanced) {
            if (b2[0] <= b1[0] && b2[1] >= b1[1] && (b2[0] !== b1[0] || b2[1] !== b1[1])) {
                isSub = true;
                break;
            }
        }
        if (!isSub) maximal.push(b1);
    }
    
    maximal.sort((a, b) => a[0] - b[0]);
    return maximal.map(b => nums.slice(b[0], b[1] + 1));
}

Related Binary Search Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Balanced Mod Subarrays

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Binary Search Challenges

Longest Mod3 Balanced Subarray

Minimize Maximum Distance Between Gas Stations

Find Target Range

Find First Greater Element

Search Insert Position

Binary Search Target Index

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.