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
By 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. This reduces the time complexity to O(n).
Optimal Approach
Iterate 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. If yes, update the maximum length with the distance between the current index and the first occurrence. If not, record the current index as the first occurrence. Return the maximum length found.
Time
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 |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int findMaxLength(int[] nums) { |
| 6 | Map<Integer, Integer> firstSeen = new HashMap<>(); |
| 7 | firstSeen.put(0, -1); |
| 8 | int score = 0; |
| 9 | int best = 0; |
| 10 | |
| 11 | for (int i = 0; i < nums.length; i++) { |
| 12 | if (nums[i] == 1) { |
| 13 | score += 1; |
| 14 | } else { |
| 15 | score -= 1; |
| 16 | } |
| 17 | |
| 18 | if (firstSeen.containsKey(score)) { |
| 19 | best = Math.max(best, i - firstSeen.get(score)); |
| 20 | } else { |
| 21 | firstSeen.put(score, i); |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | return best; |
| 26 | } |
| 27 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <algorithm> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | int findMaxLength(vector<int>& nums) { |
| 10 | unordered_map<int, int> firstSeen; |
| 11 | firstSeen[0] = -1; |
| 12 | int score = 0; |
| 13 | int best = 0; |
| 14 | |
| 15 | for (int i = 0; i < (int)nums.size(); i++) { |
| 16 | if (nums[i] == 1) { |
| 17 | score += 1; |
| 18 | } else { |
| 19 | score -= 1; |
| 20 | } |
| 21 | |
| 22 | if (firstSeen.find(score) != firstSeen.end()) { |
| 23 | best = max(best, i - firstSeen[score]); |
| 24 | } else { |
| 25 | firstSeen[score] = i; |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | return best; |
| 30 | } |
| 31 | }; |
| 1 | var findMaxLength = function(nums) { |
| 2 | const firstSeen = new Map(); |
| 3 | firstSeen.set(0, -1); |
| 4 | let score = 0; |
| 5 | let best = 0; |
| 6 | |
| 7 | for (let i = 0; i < nums.length; i++) { |
| 8 | if (nums[i] === 1) { |
| 9 | score += 1; |
| 10 | } else { |
| 11 | score -= 1; |
| 12 | } |
| 13 | |
| 14 | if (firstSeen.has(score)) { |
| 15 | best = Math.max(best, i - firstSeen.get(score)); |
| 16 | } else { |
| 17 | firstSeen.set(score, i); |
| 18 | } |
| 19 | } |
| 20 | |
| 21 | return best; |
| 22 | }; |
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
| 8 | for i in range(len(nums)): |
| 10 | if nums[i] == 1: |
| 11 | score += 1 |
| 12 | else: |
| 13 | score -= 1 |
| 15 | if score in first_seen: |
| 16 | best = max(best, i - first_seen[score]) |
| 17 | else: |
| 18 | first_seen[score] = i |
Objective
To traverse the array, update the running score based on the current element, and use the hash map to find the longest balanced subarray.
Key Insight
By treating 0 as -1 and 1 as +1, the running score reflects the net difference between counts of 1s and 0s. When the same score repeats, the subarray between the first occurrence and current index has equal numbers of 0 and 1. Updating the best length at each repetition ensures the maximum length is tracked.
Interview Quick-Check
Core Logic
The running score increments by 1 for 1 and decrements by 1 for 0, transforming the problem into finding the longest subarray with zero net sum.
State & Boundaries
Check if the current score has been seen before; if yes, update the best length using the distance between current index and first occurrence.
Common Pitfalls & Bugs
Adding the current score to the map only if it hasn't been seen before preserves the earliest index, which is essential for maximizing subarray length.
Return the Maximum Length of Balanced Subarray
| 20 | return best |
Objective
To return the length of the longest contiguous subarray with equal numbers of 0 and 1 found during iteration.
Key Insight
After processing all elements, the variable tracking the best length holds the maximum size of any balanced subarray. Returning this value completes the solution.
Interview Quick-Check
Core Logic
Returning the tracked maximum length ensures the correct answer is provided after a single pass.
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.
else:If the current score has not been seen before, record the current index as its first occurrence.
Storing only the earliest index preserves the longest possible subarray length for future matches.
return bestReturn the maximum length of a balanced subarray found.
Returning the tracked best length completes the solution, providing the correct answer after a single pass.
score = 0Initialize the running score to zero.
The running score tracks the net difference between counts of 1s and 0s, forming the basis for detecting balanced subarrays.
if nums[i] == 1:Increment the running score by 1 if the current element is 1.
Treating 1 as +1 in the running score transforms the problem into tracking net balance between 1s and 0s.
else:Decrement the running score by 1 if the current element is 0.
Treating 0 as -1 balances the score, enabling detection of equal counts via prefix sums.
first_seen[score] = iAdd the current score and index to the hash map.
This insertion enables future lookups to detect balanced subarrays starting after this index.
best = 0Initialize the variable to track the best (maximum) subarray length found so far.
This variable accumulates the maximum length of any balanced subarray encountered during iteration.
score += 1Increment the running score for 1s.
This line implements the increment operation for 1s, contributing to the net score.
score -= 1Decrement the running score for 0s.
This line implements the decrement operation for 0s, contributing to the net score.
for i in range(len(nums)):Start iterating through the array indices.
Iterating over each element allows the algorithm to update the running score and check for balanced subarrays in a single pass.
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?
Because when the same prefix sum appears again at a later index, the subarray between these two indices has a net sum of zero, indicating equal numbers of 0 and 1. Storing the earliest occurrence ensures the longest possible subarray length is computed.
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