Contiguous Array
Medium Prefix sum + first index
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a binary array, find the length of the longest contiguous subarray with equally many 0s and 1s.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: longest piece with equal 0s and 1s.
Why this works: count 0 as -1. Equal counts means the piece sums to 0, which happens when the same running sum appears twice. Remember where each sum first appeared.
Example: [0, 1, 0]
sums: -1, 0, -1 (start: 0 at index -1)index 1: sum 0 seen at -1 → length 2index 2: sum -1 seen at 0 → length 2answer 2
✦Hints open one at a time
↗Approach
Running sum with 0 → -1. A map stores the earliest index of each sum (sum 0 at index -1). When a sum repeats, the subarray from the stored index + 1 to now is balanced; keep the longest.
</>Solution (Java)
import java.util.*;
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> first = new HashMap<>();
first.put(0, -1);
int sum = 0, best = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i] == 1 ? 1 : -1;
if (first.containsKey(sum)) best = Math.max(best, i - first.get(sum));
else first.put(sum, i); // keep only the earliest index
}
return best;
}
}!Common mistake
Overwriting the stored index with later occurrences — you need the earliest to get the longest length.
- Time: O(n).
- Space: O(n).
