Problem Statement

Contiguous Array

You are given a binary array, which just means a list of numbers that are only 0s and 1s. Your job is to find the longest run of numbers, sitting next to each other, that has the same count of 0s and 1s. "Contiguous" means the numbers are right next to each other with no gaps, like a chunk you could slice out in one cut. Here is the trick we will use: pretend every 0 is actually -1. Then a chunk with equal 0s and 1s is a chunk where the numbers add up to 0, because every -1 cancels out a +1. To find such chunks fast, we use a running total called a prefix sum, which is just the sum of everything from the start up to where you are right now. The key idea: if the running total has the same value at two different spots, then everything between those two spots added up to 0, so that piece has equal 0s and 1s.

mediumPrefix SumHash TableArrays & HashingTime: O(n) · Space: O(n)

Signals to notice

longest subarray with equal 0s and 1stransform 0→-1prefix sum = 0 means equal counts

Brute force first

Check every subarray — O(n²).

The key insight

Replace 0s with -1s. Now equal 0s and 1s = sum 0. Prefix sum + hash map: same prefix at two positions = zero-sum between. O(n).

Trace it on `nums=[0,1,0,1,1,0,0]`

init: count=0, maxLen=0, firstSeen={0:-1}
i=0 num=0: count=-1 (new) -> store firstSeen[-1]=0
i=1 num=1: count=0 (seen@-1) -> maxLen=max(0,1-(-1))=2
i=2 num=0: count=-1 (seen@0) -> maxLen=max(2,2-0)=2
i=3 num=1: count=0 (seen@-1) -> maxLen=max(2,3-(-1))=4
i=4 num=1: count=1 (new) -> store firstSeen[1]=4
i=5 num=0: count=0 (seen@-1) -> maxLen=max(4,5-(-1))=6
i=6 num=0: count=-1 (seen@0) -> maxLen=max(6,6-0)=6; return 6

What must stay true

With 0→-1, equal counts ⟺ sum = 0. Same prefix sum at positions i,j means sum(i+1..j) = 0.

Shape of the loop

count = 0; maxLen = 0; firstSeen = {0: -1}
for i, num in nums:
    count += (num == 1) ? +1 : -1
    if count in firstSeen: maxLen = max(maxLen, i - firstSeen[count])
    else: firstSeen[count] = i
return maxLen

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not transforming 0s — without it, the problem is much harder. With it, it's standard prefix-sum-zero.

Arrays & Hashing Pattern