Contiguous Array

medium LeetCode #525
array hash-table prefix-sum

Description

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

Example 1:
Input: nums = [0,1]
Output: 2
Explanation: [0,1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:
Input: nums = [0,1,0]
Output: 2
Explanation: [0,1] or [1,0] are the longest with equal 0s and 1s. The entire array has 2 zeros and 1 one, so it doesn't qualify.

Example 3:
Input: nums = [0,1,1,1,1,1,0,0,0]
Output: 6
Explanation: The subarray [1,1,1,0,0,0] (indices 3-8) has 3 ones and 3 zeros.

Constraints

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

Complexity

Show Complexity
  • Time: O(n)
  • Space: O(n)

Hints

Show Hints
Pattern
Prefix sum with hash map
Approach
Replace 0 with -1. Use prefix sum - when same prefix appears twice, the subarray between has equal 0s and 1s (sum = 0). Store first occurrence of each prefix in a hash map.
Complexity
Transform 0 to -1, then find longest subarray with sum = 0

Notes

Show Notes

Contiguous Array

Problem

Find the maximum length of a contiguous subarray with an equal number of 0s and 1s.

Approach: Prefix Sum with Hash Map

Key Insight

Transform the problem:

  • Treat 0 as -1
  • Treat 1 as +1

Now “equal 0s and 1s” becomes “subarray with sum = 0”.

What is Prefix Sum Here?

prefix[i] = (count of 1s) - (count of 0s) from index 0 to i

nums:      [0,  0,  0,  1,  1,  0,  1]
as +/-:    -1  -1  -1  +1  +1  -1  +1

prefix:  0  -1  -2  -3  -2  -1  -2  -1
index:  -1   0   1   2   3   4   5   6
         ↑
    "before array"

Why prefix[-1] = 0?

Before processing any elements:

  • Count of 1s = 0
  • Count of 0s = 0
  • Prefix = 0 - 0 = 0

This handles subarrays that start from index 0.

The Core Insight: Same Prefix = Valid Subarray

If prefix[i] == prefix[j] (where j > i), then:

prefix[j] - prefix[i] = 0
(1s from i to j) - (0s from i to j) = 0
(1s from i to j) = (0s from i to j)  ← EQUAL!

Example from the trace above:

prefix:  0  -1  -2  -3  -2  -1  -2  -1
index:  -1   0   1   2   3   4   5   6
              ↑               ↑
           prefix=-1       prefix=-1

Prefix is -1 at index 0 and again at index 4.

Subarray from index 1 to 4 = [0, 0, 1, 1] → 2 zeros, 2 ones!

Length = 4 - 0 = 4

Why Store First Occurrence Only?

We want the longest subarray, so we need the earliest index for each prefix.

If prefix = -1 appears at indices 0, 4, 6:

Using first (index 0):
  - At index 4: length = 4 - 0 = 4
  - At index 6: length = 6 - 0 = 6  ← longest!

If we overwrote with latest:
  - At index 6: length = 6 - 4 = 2  ← wrong!

Step-by-Step Trace

nums = [0, 1, 0]

Setup: map = {0: -1}  ← prefix 0 first seen at index -1

i = 0, nums[0] = 0
  curr = 0 + (-1) = -1
  is -1 in map? NO → store it
  map = {0: -1, -1: 0}

i = 1, nums[1] = 1
  curr = -1 + 1 = 0
  is 0 in map? YES, at index -1
  length = 1 - (-1) = 2 ← [0,1] has equal 0s and 1s!
  max_len = 2

i = 2, nums[2] = 0
  curr = 0 + (-1) = -1
  is -1 in map? YES, at index 0
  length = 2 - 0 = 2 ← [1,0] has equal 0s and 1s!
  max_len = 2

Answer: 2

Solution

def solution(nums: list[int]) -> int:
    prefix_index = {0: -1}  # prefix value → first index
    curr = 0
    max_len = 0

    for i, num in enumerate(nums):
        curr += 1 if num else -1

        if curr in prefix_index:
            max_len = max(max_len, i - prefix_index[curr])
        else:
            prefix_index[curr] = i

    return max_len

Complexity

  • Time: O(n) - single pass through the array
  • Space: O(n) - hash map stores at most n+1 distinct prefix values

Comparison: Count vs Length Problems

GoalMap storesWhen prefix repeats
Count subarrayscount of occurrencesresult += count
Max lengthfirst indexmax_len = max(max_len, i - first_index)

Map Initialization

Always ask: “What prefix exists before the array starts?”

  • Count problem: {0: 1} → prefix 0 has occurred 1 time
  • Length problem: {0: -1} → prefix 0 first appeared at index -1

Solutions

Show PY Solution 
from collections import defaultdict


def solution(nums: list[int]) -> int:
    if len(nums) == 1:
        return 0

    m = defaultdict(int)
    m[0] = -1

    count = 0
    curr = 0
    for i in range(len(nums)):
        if nums[i] == 0:
            curr -= 1
        else:
            curr += 1
        if curr not in m:
            m[curr] = i
        count = max(count, i - m[curr])

    return count

    # count = 0
    # for i in range(len(nums)):
    #     if nums[i] == 0:
    #         curr = -1
    #     else:
    #         curr = 1
    #     j = i + 1
    #     for j in range(i + 1, len(nums)):
    #         if nums[j] == 0:
    #             curr -= 1
    #         else:
    #             curr += 1
    #     if curr == 0:
    #         count = max(count, j - i + 1)
    #
    # return count
    #