This problem requires tracking the balance between 0s and 1s across a binary array. By converting 0s to -1s and using a running prefix sum with a hash map, you can efficiently find subarrays that sum to zero. This approach avoids nested loops and ensures linear time complexity, making it suitable for large arrays while minimizing space overhead.
Problem Statement
Given a binary array nums, return the maximum length of a contiguous subarray where the number of 0s and 1s are equal. The array contains only 0s and 1s and can be large, so an efficient linear-time solution is expected.
For example, in nums = [0,1,0,1,1,0,0], the longest contiguous subarray with equal 0s and 1s is [0,1,0,1] or [1,0,1,0], both having length 4. You need to return the length of such a subarray, not the subarray itself.
Examples
Example 1
Input: nums = [0,1]
Output: 2
[0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2
Input: nums = [0,1,0]
Output: 2
[0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Example 3
Input: nums = [0,1,1,1,1,1,0,0,0]
Output: 6
[1,1,1,0,0,0] is the longest contiguous subarray with equal number of 0 and 1.
Constraints
- 1 <= nums.length <= 105
- nums[i] is either 0 or 1.
Solution Approach
Convert 0s to -1s and compute prefix sum
Transform each 0 in the array to -1 so that a subarray with equal 0s and 1s sums to zero. Use a running prefix sum to track cumulative totals as you iterate through the array.
Use hash map to store first occurrence
Maintain a hash map to store the first index where each prefix sum occurs. If the same sum appears again, the subarray between the two indices has a net sum of zero, indicating equal numbers of 0s and 1s.
Update maximum length efficiently
During iteration, whenever a prefix sum repeats, calculate the subarray length from the previous index to the current index and update the maximum length. This ensures O(n) time without scanning all subarrays.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because each element is scanned once and hash map operations are O(1) on average. Space complexity is O(n) to store prefix sums in the hash map, which is necessary for efficient lookups.
What Interviewers Usually Probe
- You may notice that a naive double loop approach times out for large arrays.
- Converting 0s to -1s is a common hint that this is a prefix sum pattern.
- Hash map usage suggests tracking first occurrences to maximize subarray length.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to convert 0s to -1s, which breaks the sum-to-zero pattern.
- Overwriting the first occurrence of a prefix sum in the hash map, which can underestimate the maximum length.
- Trying to return the subarray itself instead of just its length, adding unnecessary complexity.
Follow-up variants
- Count the number of contiguous subarrays with equal 0s and 1s instead of maximum length.
- Handle arrays with more than two binary values, e.g., 0,1,2, requiring multiple prefix sums.
- Find maximum length subarray with equal numbers of two specific elements in a non-binary array.
How GhostInterview Helps
- Automatically identifies prefix sum plus hash table patterns to guide array scanning efficiently.
- Highlights potential pitfalls such as overwriting first occurrences or ignoring 0-to--1 conversion.
- Calculates maximum length subarrays without manual debugging, saving time during coding interviews.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
Why do we convert 0s to -1s in the Contiguous Array problem?
Converting 0s to -1s allows the prefix sum to reflect net balance; a sum of zero indicates equal numbers of 0s and 1s.
Can we solve this without using a hash map?
Without a hash map, you'd need a nested loop to check all subarrays, which results in O(n^2) time and is inefficient for large arrays.
What is the time and space complexity of this solution?
Time complexity is O(n) for a single pass, and space complexity is O(n) due to storing prefix sums in a hash map.
How does the hash map help find the maximum length subarray?
It records the first index of each prefix sum. When a sum repeats, the subarray between indices sums to zero, showing equal 0s and 1s.
Can this pattern apply to other problems?
Yes, the array scanning plus hash lookup pattern generalizes to any problem tracking cumulative counts to identify equal distribution subarrays.
Need direct help with Contiguous Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Contiguous Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Identify if any continuous subarray sums to a multiple of k using prefix sums and hash table tracking efficiently.
Open problem page#560 Subarray Sum Equals KCount the total number of contiguous subarrays in an integer array that sum exactly to a target value k using optimized scanning.
Open problem page#930 Binary Subarrays With SumCount all contiguous subarrays in a binary array whose elements sum exactly to a given goal using prefix sums efficiently.
Open problem page