Balanced Mod Subarrays

Like20

In Balanced Mod Subarrays, you work with an integer list and split each number by its remainder modulo 3, so every value belongs to class 0, 1, or 2. Your goal is to return contiguous segments where those three classes appear in equal counts. The important part is that the task asks for inclusion-maximal balanced segments, meaning each returned segment cannot be extended left or right and still stay balanced.

A practical way to think about this is counting remainder frequencies inside candidate windows, then validating balance and maximality before adding them to output. Negative numbers still need correct modulo handling, so your implementation should normalize remainder calculation consistently across languages.

The judge checks both simple and dense inputs, including empty arrays and data where many overlapping balanced windows exist. Output order matters: keep segments in the same order they appear in the original sequence. Your return value should contain only valid maximal balanced subarrays, with no duplicates and no smaller subsegments that are fully contained inside a larger balanced segment.

Because this is a counting/optimization-style challenge, dynamic programming is usually the safest approach: define what each index or state means, initialize valid base states, and make transitions explicit. If the problem uses modulo arithmetic, apply modulo at every accumulation step so large intermediate totals never corrupt the final answer.

Examples

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 - Budibadu

Best Answers

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

Comments (0)

Join the Discussion

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

Balanced Mod Subarrays

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Binary Search Problems

Festival Drone Altitude Limit

Lantern Stage Volume Check

Pier Ticket Window Time

Harbor Relay Coverage Radius

Marina Beacon Frequency Search

Minimal Climb Cost

Comments (0)

Join the Discussion