DSA-031 · Earliest repeated prefix balance

Contiguous Array — Equal Zeroes and Ones

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 8198 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the longest contiguous subarray containing equally many zeros and ones.

nums is non-null with 0–100,000 entries. Both methods throw IllegalArgumentException if any value is not 0 or 1. Input is preserved; validation does not rewrite zeros into -1.
Return the maximum length, or 0 if no nonempty balanced subarray exists. Empty input returns 0. Equal counts are required, not merely the presence of both symbols.
Use prefix boundaries 0..n: boundary zero precedes the first element. Store the earliest boundary for each balance, seeded with balance 0 at boundary 0. This is equivalent to an element-index implementation seeded at virtual index -1; do not mix the two formulas.

Examples

Input: [0,1,0]
Output: 2
Either [0,1] or [1,0] has one occurrence of each symbol.
Input: [0,0,1,0,1,1]
Output: 6
The entire array has three zeros and three ones.

Before you start

Array positions versus prefix boundaries and half-open intervals
Long arithmetic, frequency maps, and invariant reasoning

Recognize the structure

Equal symbol counts become a zero transformed sum when zeros contribute -1 and ones contribute +1. Repeated prefix balances isolate such ranges. For longest length, the earliest occurrence of a balance is the useful state, rather than its frequency or latest position.

Try before revealing

Hint 1

What signed contribution makes equal zero/one counts sum to zero?

Hint 2

Equal balances at two boundaries identify which interval?

Hint 3

Store the earliest boundary for each balance and maximize their distance.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Count both symbols for every start

For every start, extend end while updating zero and one counters; record a length when the counts match. On [0,1,0], start zero gives [0,1] of length two, while start one gives [1,0] of length two. This O(n²) time, O(1) space baseline expresses the original equality directly without transforming the input.

Improve the baseline

Transform logically

Let balance count ones minus zeros in the processed prefix. A range has equal counts exactly when its transformed sum is zero.

Compare boundary balances

If balances at boundaries a and b are equal, the intervening [a,b) has net balance zero and length b-a. Seed earliest[0]=0 to include ranges beginning at the first element.

Keep only the earliest occurrence

For current boundary b=i+1, an earlier matching boundary gives a longer range than a later one. Insert a new balance only if absent; otherwise compare b-earliest[balance] with best.

Why it is correct

Prefix identity

After processing i, balance equals ones-minus-zeros in nums[0..i+1). Subtracting two such balances gives the same quantity for the intervening range, so equality is equivalent to balanced counts.

Earliest dominance

For a fixed ending boundary b and balance v, b-a is largest when matching a is smallest. A later occurrence of v can never improve any future longest-length query, so discarding it preserves all optima.

Coverage and initialization

Every nonempty candidate ends at one of the visited boundaries 1..n. The seed at zero handles balanced prefixes; every ending boundary uses its longest possible matching start. Taking their maximum is globally optimal and the scan terminates after n steps.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.HashMap;
import java.util.Map;
public final class Solution {
    private static void validate(int[] nums) {
        for (int value : nums) if (value != 0 && value != 1) throw new IllegalArgumentException("binary input required");
    }
    public static int findMaxLength(int[] nums) {
        validate(nums);
        Map<Integer, Integer> earliest = new HashMap<>();
        earliest.put(0, 0);
        int balance = 0, best = 0;
        for (int i = 0; i < nums.length; i++) {
            balance += nums[i] == 0 ? -1 : 1;
            Integer first = earliest.putIfAbsent(balance, i + 1);
            if (first != null) best = Math.max(best, i + 1 - first);
        }
        return best;
    }
    public static int baseline(int[] nums) {
        validate(nums);
        int best = 0;
        for (int start = 0; start < nums.length; start++) {
            int zeroes = 0, ones = 0;
            for (int end = start; end < nums.length; end++) {
                if (nums[end] == 0) zeroes++; else ones++;
                if (zeroes == ones) best = Math.max(best, end - start + 1);
            }
        }
        return best;
    }
}

Read the meaningful blocks

putIfAbsent preserves ownership

Its returned old value is the earliest boundary when present; replacing it would shorten future candidates.

Use boundary i+1

This pairs with the zero-boundary seed. An index -1 seed would require i-first instead.

Validate without mutation

Computing -1/+1 contributions in a local balance preserves the caller’s binary array.

Complexity

Expected O(n) time including validation and hash-map operations. O(n) auxiliary storage for at most n+1 distinct prefix balances; the length fits int.

The direct-count baseline uses O(n²) time and O(1) space. A deterministic array indexed by balance+n can also achieve O(n) time using O(n) allocated slots, because balance lies in [-n,n].

Exact-state walkthroughs

Reveal normal and boundary traces

Never replace the earliest matching boundary

Input: {"nums":[0,1,0,1,1,0]} · Result: 6

Step 1 of 8: Seed balance zero at the empty prefix boundary.

Each stored boundary is the earliest occurrence of its balance.

Binary input — processed prefix or matching-balance candidate

0: 0
1: 1
2: 0
3: 1
4: 1
5: 0

Balance → earliest prefix boundary (never overwritten)

0 → 0

State after this step
Variable	Value
values	`[0,1,0,1,1,0]`
boundary	`0`
balance	`0`
best	`0`
earliestBoundaries	`[[0,0]]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.Map;
 3 public final class Solution {
 4     private static void validate(int[] nums) {
 5         for (int value : nums) if (value != 0 && value != 1) throw new IllegalArgumentException("binary input required");
 6     }
 7     public static int findMaxLength(int[] nums) {
 8         validate(nums);
 9         Map<Integer, Integer> earliest = new HashMap<>();
10         earliest.put(0, 0);
11         int balance = 0, best = 0;
12         for (int i = 0; i < nums.length; i++) {
13             balance += nums[i] == 0 ? -1 : 1;
14             Integer first = earliest.putIfAbsent(balance, i + 1);
15             if (first != null) best = Math.max(best, i + 1 - first);
16         }
17         return best;
18     }
19     public static int baseline(int[] nums) {
20         validate(nums);
21         int best = 0;
22         for (int start = 0; start < nums.length; start++) {
23             int zeroes = 0, ones = 0;
24             for (int end = start; end < nums.length; end++) {
25                 if (nums[end] == 0) zeroes++; else ones++;
26                 if (zeroes == ones) best = Math.max(best, end - start + 1);
27             }
28         }
29         return best;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed balance zero at the empty prefix boundary.
Each stored boundary is the earliest occurrence of its balance.
values
[0,1,0,1,1,0]
boundary
0
balance
0
best
0
earliestBoundaries
[[0,0]]
Own this balance at its first boundary.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,1,0,1,1,0]
boundary
1
balance
-1
best
0
earliestBoundaries
[[0,0],[-1,1]]
i
0
first
null
candidateLength
0
Use the earliest matching boundary without replacing it.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,1,0,1,1,0]
boundary
2
balance
0
best
2
earliestBoundaries
[[0,0],[-1,1]]
i
1
first
0
candidateLength
2
Use the earliest matching boundary without replacing it.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,1,0,1,1,0]
boundary
3
balance
-1
best
2
earliestBoundaries
[[0,0],[-1,1]]
i
2
first
1
candidateLength
2
Use the earliest matching boundary without replacing it.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,1,0,1,1,0]
boundary
4
balance
0
best
4
earliestBoundaries
[[0,0],[-1,1]]
i
3
first
0
candidateLength
4
Own this balance at its first boundary.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,1,0,1,1,0]
boundary
5
balance
1
best
4
earliestBoundaries
[[0,0],[-1,1],[1,5]]
i
4
first
null
candidateLength
0
Use the earliest matching boundary without replacing it.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,1,0,1,1,0]
boundary
6
balance
0
best
6
earliestBoundaries
[[0,0],[-1,1],[1,5]]
i
5
first
0
candidateLength
6
Return the contract result.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
result
6

One symbol gives no repeated balance

Input: {"nums":[0,0,0]} · Result: 0

Step 1 of 5: Seed balance zero at the empty prefix boundary.

Each stored boundary is the earliest occurrence of its balance.

Binary input — processed prefix or matching-balance candidate

0: 0
1: 0
2: 0

Balance → earliest prefix boundary (never overwritten)

0 → 0

State after this step
Variable	Value
values	`[0,0,0]`
boundary	`0`
balance	`0`
best	`0`
earliestBoundaries	`[[0,0]]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.Map;
 3 public final class Solution {
 4     private static void validate(int[] nums) {
 5         for (int value : nums) if (value != 0 && value != 1) throw new IllegalArgumentException("binary input required");
 6     }
 7     public static int findMaxLength(int[] nums) {
 8         validate(nums);
 9         Map<Integer, Integer> earliest = new HashMap<>();
10         earliest.put(0, 0);
11         int balance = 0, best = 0;
12         for (int i = 0; i < nums.length; i++) {
13             balance += nums[i] == 0 ? -1 : 1;
14             Integer first = earliest.putIfAbsent(balance, i + 1);
15             if (first != null) best = Math.max(best, i + 1 - first);
16         }
17         return best;
18     }
19     public static int baseline(int[] nums) {
20         validate(nums);
21         int best = 0;
22         for (int start = 0; start < nums.length; start++) {
23             int zeroes = 0, ones = 0;
24             for (int end = start; end < nums.length; end++) {
25                 if (nums[end] == 0) zeroes++; else ones++;
26                 if (zeroes == ones) best = Math.max(best, end - start + 1);
27             }
28         }
29         return best;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed balance zero at the empty prefix boundary.
Each stored boundary is the earliest occurrence of its balance.
values
[0,0,0]
boundary
0
balance
0
best
0
earliestBoundaries
[[0,0]]
Own this balance at its first boundary.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,0,0]
boundary
1
balance
-1
best
0
earliestBoundaries
[[0,0],[-1,1]]
i
0
first
null
candidateLength
0
Own this balance at its first boundary.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,0,0]
boundary
2
balance
-2
best
0
earliestBoundaries
[[0,0],[-1,1],[-2,2]]
i
1
first
null
candidateLength
0
Own this balance at its first boundary.
Equal balances enclose equal zero/one counts; the earliest start maximizes distance for this and every later endpoint.
values
[0,0,0]
boundary
3
balance
-3
best
0
earliestBoundaries
[[0,0],[-1,1],[-2,2],[-3,3]]
i
2
first
null
candidateLength
0
Return the contract result.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
result
0

Test the contract

Input: []
Output: 0
No nonempty balanced range.
Input: [0,0,0]
Output: 0
Only one symbol appears.
Input: [0,1,0,1]
Output: 4
Earliest repeated zero balance matters.
Input: [0,2]
Output: IllegalArgumentException
The binary domain is enforced.

Common mistakes and counterexamples

Overwrite an existing earliest boundary

Counterexample: [0,1,0,1] needs the initial zero boundary to recover length four.

Insert only if absent.

Omit the zero boundary

Counterexample: [0,1] is balanced from the start.

Seed earliest[0]=0 when using boundary lengths.

Count matching balances instead of measuring distance

Counterexample: The number of balanced ranges and longest length differ.

Store earliest positions for length; frequencies solve the counting variant.

Follow-ups

Count all balanced subarrays.

Store the frequency of every earlier balance and add that frequency when a balance repeats. Seed zero once and query before inserting the current boundary; a set or earliest-only map cannot count multiplicities.

Equalize three symbols.

Track a pair of differences, such as countA-countC and countB-countC. Repeated difference pairs identify ranges with all three counts equal; hash an unambiguous pair key and retain its earliest boundary.

Process an unbounded stream.

Balances can keep creating new keys, so exact earliest-state memory is not generally constant. A bounded history changes the question to a rolling horizon and requires expiring old boundary candidates carefully.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 127/20,000 characters

Self-review

I can derive the signed transformation.I keep the earliest boundary and its seed.I distinguish longest length from counting.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Prefix sums: boundaries and multiplicity

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.