Contiguous Array

Problem

Given a binary array nums containing only 0s and 1s, return the length of the longest contiguous subarray that contains the same number of 0s as 1s. If no such subarray exists, return 0.

• The array is non-empty and has at most 200,000 elements.
• Every element is 0 or 1.

Examples

• nums = [1, 0, 0, 1, 1, 0, 1] → 6. The first six elements hold three 0s and three 1s; the whole array does not.
• nums = [1, 1, 0, 1] → 2. Either [1,0] or [0,1]; nothing longer balances.
• nums = [0, 0, 0, 0] → 0. No 1s at all, so no balanced subarray.

Hints

1. "Equal number of 0s and 1s" is a statement about a count difference. Can you turn the array into something whose sum expresses that difference?
2. Replace each 0 with -1. A subarray is balanced exactly when its sum is 0.
3. A subarray sums to 0 when two prefix sums are equal. Remember where each prefix sum first appeared.