#525

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Contiguous Array

Find the maximum length contiguous subarray with equal numbers of 0s and 1s using array scanning and hash lookup efficiently.

array hash table prefix sum

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.

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.

terminal

Solution

Solution 1: Prefix Sum + Hash Table

According to the problem description, we can treat $0$s in the array as $-1$. In this way, when encountering a $0$, the prefix sum $s$ will decrease by one, and when encountering a $1$, the prefix sum $s$ will increase by one. Therefore, suppose the prefix sum $s$ is equal at indices $j$ and $i$, where $j < i$, then the subarray from index $j + 1$ to $i$ has an equal number of $0$s and $1$s.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        d = {0: -1}
        ans = s = 0
        for i, x in enumerate(nums):
            s += 1 if x else -1
            if s in d:
                ans = max(ans, i - d[s])
            else:
                d[s] = i
        return ans

Continue Practicing

#523 continuous subarray sum #560 subarray sum equals k #930 binary subarrays with sum