Coding Interview PatternsContiguous Array
MediumHash Maps

Contiguous Array

Explanation & Solution

Practice Problem

Description

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Input:nums = [0, 1]
0
0
1
1

Output: 2

Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Constraints

  • 1 <= nums.length <= 10⁵
  • nums[i] is either 0 or 1

Approach

Hash Maps pattern

1. Transform the Problem

  • Treat each 0 as -1 and each 1 as +1
  • Now the problem becomes: find the longest subarray with a sum of 0
  • This is equivalent to finding equal numbers of 0s and 1s

2. Use a Prefix Sum with a Hash Map

  • Maintain a running count (prefix sum) as we scan left to right
  • Create a hash map prefixMap that maps each prefix sum value to the earliest index where it occurred
  • Initialize with prefixMap.set(0, -1) to handle the case where the subarray starts from index 0

3. Scan Through the Array

  • For each index i, update count: add +1 for 1, add -1 for 0
  • If count has been seen before at index j, then the subarray from j+1 to i has a sum of 0, meaning equal 0s and 1s
  • Update maxLen = Math.max(maxLen, i - j)
  • If count has not been seen before, store the current index as its first occurrence

4. Return the Maximum Length

  • After processing all elements, maxLen holds the length of the longest contiguous subarray with equal 0s and 1s

Key Insight

  • If the prefix sum at index i equals the prefix sum at index j, then the elements between j+1 and i must sum to 0 — meaning equal counts of 0 and 1
  • We only store the first occurrence of each prefix sum to maximize the subarray length
Time
O(n)single pass through the array
Space
O(n)the hash map stores at most n+1 distinct prefix sums

Visualization

Input:
[0, 1]
0011
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
4Sum II
Next
Brick Wall