Contiguous Array Solution

Problem

Given a binary array containing only 0s and 1s, find the length of the longest contiguous subarray that has an equal number of 0s and 1s.

Input: nums = [0, 1, 0, 1]
Output: 4
Explanation: The entire array contains two 0s and two 1s, so the full array is the longest balanced subarray.

Counter-example: nums = [1, 1, 0, 1, 1] → 2. With four 1s and one 0 it's impossible to balance more than two elements, so the longest balanced subarray is just [1, 0] or [0, 1].

Intuition

A balanced subarray has equal 0s and 1s. The trick that makes this tractable is replacing every 0 with -1 — then "equal counts" becomes "sum equals zero." That transforms the problem into finding the longest subarray with sum zero, a classic prefix-sum question. Two positions with the same prefix sum mark the endpoints of a zero-sum stretch, and a hash map that records the first time each prefix sum appears lets us compute that length in O(1) per position.

Approach 1 — Brute Force

Fix a left boundary and sweep the right boundary, tracking zero and one counts as we go.

Iterate over every possible left boundary.
Reset zero and one counters at each new left boundary.
Extend the right boundary from there to the end, updating the counts with each element.
Whenever the counts are equal, update the maximum length.
Return the maximum.

1def findMaxLength(nums: list[int]) -> int:
2    max_len = 0
3    for left in range(len(nums)):
4        zero_count = 0
5        one_count = 0
6        for right in range(left, len(nums)):
7            if nums[right] == 0:
8                zero_count += 1
9            else:
10                one_count += 1
11            if zero_count == one_count:
12                max_len = max(max_len, right - left + 1)
13    return max_len

Time: O(n²) — every pair of (left, right) indices is visited once.
Space: O(1) — only a handful of scalar counters beyond the input.

Approach 2 — Prefix Sum with Hash Map

Treat 0 as -1, accumulate a running prefix sum, and record the earliest index where each prefix sum value first appears.

Initialize a hash map with {0: -1} — this represents the empty prefix at virtual index -1 so that balanced subarrays starting at index 0 are detected correctly.
Walk through the array, adding +1 for each 1 and -1 for each 0 to a running prefix sum.
If the current prefix sum has been seen before, the subarray from just after that first-seen index to the current index is balanced — update the maximum length.
If the current prefix sum has not been seen before, record it in the map with the current index.
Return the maximum length.

1def findMaxLength(nums: list[int]) -> int:
2    first_seen = {0: -1}   # prefix_sum → earliest index where it appeared
3    prefix_sum = 0
4    max_len = 0
5
6    for i, val in enumerate(nums):
7        prefix_sum += 1 if val == 1 else -1   # treat 0 as -1 so equal counts → sum zero
8        if prefix_sum in first_seen:
9            max_len = max(max_len, i - first_seen[prefix_sum])
10        else:
11            first_seen[prefix_sum] = i   # store only the first occurrence to maximize length
12
13    return max_len

Time: O(n) — a single pass with O(1) hash map operations at each step.
Space: O(n) — the map holds at most one entry per distinct prefix sum value, and there are at most 2n + 1 possible values.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Very small inputs or when no extra memory is available
Prefix Sum + Hash Map	O(n)	O(n)	Standard choice — the O(n) space is easily worth the speedup

Common Mistakes

Not seeding the map with {0: -1} — without this initialization, a balanced subarray that starts at index 0 is never detected, because there's no earlier recorded entry for prefix sum 0 to compare against.
Overwriting the map entry when the same prefix sum appears again — you must store only the first occurrence of each prefix sum. Updating it on every visit moves the anchor forward, shortening the computed subarray length and giving a wrong (too small) answer.
Keeping 0s as 0 instead of converting them to -1 — using the original values makes the prefix sum only grow or stay flat, so two positions share a prefix sum only when nothing was added between them, not when there's a balanced section. The -1 substitution is essential.
Computing length as i - first_seen[sum] + 1 — the balanced subarray runs from first_seen[sum] + 1 to i inclusive, so its length is i - first_seen[sum]. Adding 1 would incorrectly include the position where the anchor prefix sum was first seen.
Tracking zero and one counts as a pair in the hash map — storing pairs (zero_count, one_count) as keys would work but duplicates all the state that a single running difference already captures; it also makes the key space harder to reason about and doesn't simplify the algorithm.

Contiguous Array — Solution