Prefix Sum — Contiguous Array
↗ LeetCode: Contiguous Array · Medium · pattern chapter →
Asked atMetaAmazonGoogle
Given binary array nums, return the length of the longest subarray with equal numbers of 0s and 1s.
Example 1 — nums = [0,1] → 2Example 2 — nums = [0,1,0] → 2Example 3 — nums = [0,0,1,1,0] → 4
Constraints — 1 ≤ n ≤ 10⁵; nums[i] ∈ {0,1}. Brute is O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Rewrite as prefix-sum with 0/1→−1/+1, hashmap of first-seen index → O(n) = 10⁵ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Every subarray
O(n²). Baseline.
Approach 2 — Map 0 → −1; prefix-sum with earliest-index map
Insight. Replace 0 with −1. Equal counts of 0/1 iff running sum returns to a prior value. Store first occurrence of each prefix sum; on revisit, subarray length = i - firstIndex.
java
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] == 0) ? -1 : 1;
if (first.containsKey(sum)) best = Math.max(best, i - first.get(sum));
else first.put(sum, i);
}
return best;
}Execution Trace
Step 1 / 4first -1 at 0
Complexity — Time O(n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute | O(n²) | O(1) | baseline |
| Prefix + first-index map | O(n) | O(n) | optimum |
When to use which
- Equal count of two labels → 0→−1 mapping + first-index.
- Longest subarray with sum S → same skeleton, store first prefix by value.
- k different labels equal counts → k-dimensional signature as hash key.
AI Study CompanionBeta
Related problems
Was this page helpful?