Contiguous Array
Problem
nums (only 0s and
1s). Return the length of the longest contiguous subarray containing
the same number of 0s and 1s, or 0 if none exists.[0,1]Output2[0,1,0]Output2[0,1,1,1,1,1,0,0,0]Output61 ≤ n ≤ 105 · nums[i] ∈ {0, 1}
Try it yourself
class Solution {
public int findMaxLength(int[] nums) {
}
}
0 as -1 and a 1 as +1.
“Equal 0s and 1s” becomes “sum = 0”, i.e. two positions with the
same running balance. Remember where each balance first appeared.Instinct Repeated range-sum queries, or "count subarrays whose sum equals / divides K" with negatives allowed? Store running totals and subtract two of them.
Memory hack Any range is two prefixes apart - sum(i..j) = P[j+1] - P[i], so remember every P you've passed.
Open the Prefix Sum guide →Approaches
Brute ForceCount Every Subarray
O(n3)Space O(1)For every (start, end) pair, count the zeros and ones inside
with a fresh loop. If the counts match, update the best length.
public int findMaxLength(int[] nums) { int best = 0; for (int start = 0; start < nums.length; start++) { for (int end = start; end < nums.length; end++) { int zeros = 0, ones = 0; for (int m = start; m <= end; m++) { if (nums[m] == 0) zeros++; else ones++; } if (zeros == ones) best = Math.max(best, end - start + 1); } } return best; }
Direct translation of the statement; cubic and hopeless at 105.
BetterRunning Balance per Start
O(n2)Space O(1)Fix start and grow end, updating a balance
(+1 for 1, -1 for 0) incrementally. Whenever the balance
returns to 0, [start..end] is balanced.
public int findMaxLength(int[] nums) { int best = 0; for (int start = 0; start < nums.length; start++) { int balance = 0; for (int end = start; end < nums.length; end++) { balance += nums[end] == 0 ? -1 : 1; if (balance == 0) best = Math.max(best, end - start + 1); } } return best; }
Drops the inner recount, but still ~1010 steps at n = 105.
OptimalPrefix Balance + First-Index Map
O(n)Space O(n)If the running balance at i equals the balance at an earlier
j, then (j..i] sums to 0. To maximise
i - j, store only the first index of each balance. Seeding
{0: -1} handles subarrays that start at index 0.
public int findMaxLength(int[] nums) { Map<Integer, Integer> first = new HashMap<>(); first.put(0, -1); // balance 0 "before" index 0 int best = 0, balance = 0; for (int i = 0; i < nums.length; i++) { balance += nums[i] == 0 ? -1 : 1; Integer j = first.putIfAbsent(balance, i); if (j != null) best = Math.max(best, i - j); } return best; }
Dry run[0,1,1,1,0,0]
- i=00i11100bal=-1 new
- i=101i1100bal=0 @-1 → len 2
- i=2011i100bal=1 new
- i=30111i00bal=2 new
- i=4011j10i0bal=1 @2 → len 2
- i=5011100ibal=0 @-1 → 6 ✔
Single pass; at most 2n+1 distinct balances in the map.
[-n, n], so an int[2n+1] (offset by
n) can replace the map for a faster constant.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Count Every Subarray | O(n3) | O(1) |
| Better | Running Balance per Start | O(n2) | O(1) |
| Optimal | Prefix Balance + First-Index Map | O(n) | O(n) |
- Overwriting the stored index — keep the first occurrence to get the longest span.
- Missing the
{0: -1}seed → balanced prefixes like[0,1]are lost. - Length is
i - j, noti - j + 1(jis before the subarray).
- Say the ±1 transformation out loud — it reduces the problem to “sum = 0”.
- Contrast with Subarray Sum = K: here store first index (longest), there store counts.
- Offer the array-instead-of-map optimisation as a follow-up.