Contiguous Array
mediumTime: 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).
What must stay true
With 0→-1, equal counts ⟺ sum = 0. Same prefix sum at positions i,j means sum(i+1..j) = 0.
Easy way to go wrong
Not transforming 0s — without it, the problem is much harder. With it, it's standard prefix-sum-zero.