Contiguous Array
Problem
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
- 1 ≤ nums.length ≤ 10⁵
- nums[i] is either 0 or 1
Example
nums = [0,1,0]2The brute-force approach would check every possible subarray and count zeros and ones, resulting in O(n²) time complexity. Instead, the algorithm transforms the problem by treating 0 as -1 and 1 as +1, then uses a prefix sum to track the cumulative score. When the same score appears twice, it means the subarray between those indices has equal numbers of 0 and 1. For example, at index 0, score is -1; at index 1, score is 0 again, indicating the subarray from index 0 to 1 has equal zeros and ones. The algorithm records the earliest occurrence of each score in a hash map to quickly compute the maximum length.
Approach
Straightforward Solution
A brute-force approach would check all subarrays, counting zeros and ones each time, resulting in O(n²) time complexity, which is inefficient for large inputs.
Core Observation
The key insight is that equal numbers of 0 and 1 in a subarray correspond to a net zero sum when 0 is treated as -1 and 1 as +1. Thus, the problem reduces to finding the longest subarray with a cumulative sum of zero.
Path to Optimal
PreviewBy converting 0s to -1s, the problem becomes finding the longest subarray with a prefix sum that repeats. Using a hash map to store the first occurrence of each prefix sum allows constant-time lookups to find the longest subarray with zero net sum…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through the array, updating a running score (+1 for 1, -1 for 0). For each score, check if it has been seen before in the hash map…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm makes a single pass through the array, performing constant-time operations for each element, including hash map lookups and updates.
Space
O(n)
In the worst case, the hash map stores a unique prefix sum for each index, requiring O(n) auxiliary space.
Pattern Spotlight
Hash Maps (Prefix Sum with First Occurrence Tracking)
When searching for the longest subarray with a certain cumulative property, transform the problem into prefix sums and use a hash map to record the earliest index of each prefix sum, enabling O(1) lookups to find subarrays with desired sums.
Solution
| 1 | class Solution: |
| 2 | def findMaxLength(self, nums: List[int]) -> int: |
| 3 | |
| 4 | first_seen = {0: -1} |
| 5 | score = 0 |
| 6 | best = 0 |
| 7 | |
| 8 | for i in range(len(nums)): |
| 9 | |
| 10 | if nums[i] == 1: |
| 11 | score += 1 |
| 12 | else: |
| 13 | score -= 1 |
| 14 | |
| 15 | if score in first_seen: |
| 16 | best = max(best, i - first_seen[score]) |
| 17 | else: |
| 18 | first_seen[score] = i |
| 19 | |
| 20 | return best |
Step-by-Step Solution
Initialize Prefix Sum Map and Tracking Variables
| 4 | first_seen = {0: -1} |
| 5 | score = 0 |
| 6 | best = 0 |
Objective
To set up a hash map to record the earliest index of each prefix sum and initialize variables to track the running score and best subarray length.
Key Insight
Initializing the hash map with score 0 mapped to index -1 handles the edge case where a valid subarray starts at index 0. The running score accumulates +1 for each 1 and -1 for each 0, enabling detection of balanced subarrays via repeated scores.
Interview Quick-Check
Core Logic
The hash map stores the earliest index where each prefix sum occurs, enabling O(1) lookups to find subarrays with zero net sum.
State & Boundaries
Mapping score 0 to index -1 allows subarrays starting at index 0 to be correctly measured.
Common Pitfalls & Bugs
Forgetting to initialize the hash map with {0: -1} causes incorrect length calculations for subarrays starting at the beginning.
Iterate Through Array and Update Running Score
To traverse the array, update the running score based on the current element, and use the hash map to find the longest balanced subarray.
Return the Maximum Length of Balanced Subarray
To return the length of the longest contiguous subarray with equal numbers of 0 and 1 found during iteration.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
first_seen = {0: -1}Initialize a hash map to record the earliest index of each prefix sum, starting with score 0 at index -1.
Mapping score 0 to index -1 is critical to correctly handle subarrays starting at index 0, enabling the algorithm to measure lengths from the start without special cases.
if score in first_seen:Check if the current running score has been seen before in the hash map.
Detecting repeated scores indicates a balanced subarray between the first occurrence and current index.
best = max(best, i - first_seen[score])Update the best length with the maximum of current best and the distance between current index and first occurrence of the score.
Calculating the subarray length from the earliest occurrence to current index ensures the longest balanced subarray is tracked.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does storing the first occurrence of each prefix sum enable finding the longest subarray with equal numbers of 0 and 1?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Contiguous Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Contiguous Array drill