Contiguous Array

This problem hides a prefix sum behind a counting question. Nothing in the statement mentions sums, and the numbers are only 0 and 1. The move that unlocks it is a small re-labelling, and interviewers ask it precisely to see whether you can spot a known pattern in unfamiliar clothes.

It is also the cleanest example of the "longest" form of the pattern. Where Subarray Sum Equals K stored how many times each prefix appeared, this one stores where it first appeared — because the earliest start gives the longest subarray.

The problem

Given a list containing only 0s and 1s, return the length of the longest contiguous subarray that has the same number of 0s as 1s. Return 0 if there is none.

• [0, 0, 1, 0, 1, 1, 1] → 6. Indices 0 to 5 hold 0, 0, 1, 0, 1, 1: three of each.
• [1, 1, 1] → 0. There are no 0s at all.

Constraints: 1 ≤ n ≤ 10⁵, and every element is 0 or 1.

Clarifying questions

• Return the length or the subarray? The length. (Returning the bounds is the same code, tracking two indices.)
• Contiguous only? Yes. If any subset were allowed, the answer would just be 2 × min(zeros, ones).
• What if no such subarray exists? Return 0.
• Only 0 and 1? Yes. Other values would need a different mapping.

Approach 1: the simple way

Try every start, extend the end, and track a balance: +1 for each 1, −1 for each 0. When the balance is 0, the counts are equal.

1def find_max_length_brute(nums: list[int]) -> int:2    """Try every start, extend the end, track zeros minus ones."""3    best = 04    for start in range(len(nums)):5        balance = 06        for end in range(start, len(nums)):7            balance += 1 if nums[end] == 1 else -18            if balance == 0:9                best = max(best, end - start + 1)10    return best

Time is O(n²), space O(1). At n = 10⁵ that is about 5 × 10⁹ inner steps. Too slow, and the brute force already shows the way forward: it is computing a running balance, which is a prefix sum.

The key insight

Count every 0 as −1. Now "as many 0s as 1s" means "the −1s and +1s cancel", which means "the subarray sums to 0".

A subarray from i to j sums to 0 exactly when the running balance before i equals the running balance after j. In prefix terms, prefix[j + 1] - prefix[i] = 0, so prefix[i] = prefix[j + 1]. Two positions with the same balance bound a balanced subarray.

We want the longest one. For a given end j, the best start is the earliest position that had the same balance. So remember only the first index at which each balance appeared, and never overwrite it: a later index can only give a shorter subarray.

The seed follows from the same reasoning as in Subarray Sum Equals K. Before index 0 the balance is 0, and that empty prefix "happened" at position −1. So the map starts as {0: -1}, and a subarray starting at index 0 gets length j - (-1) = j + 1.

Walking along, the balance changes by exactly 1 per step. It is like tracking a lift that goes up one floor for each 1 and down one floor for each 0: every time the lift returns to a floor it has visited before, the trip in between had equal ups and downs.

Approach 2: first index of each balance

1def find_max_length(nums: list[int]) -> int:2    """Longest subarray with as many 0s as 1s."""3    first_seen = {0: -1}        # balance 0 happens before index 04    balance = 05    best = 06    for i, value in enumerate(nums):7        balance += 1 if value == 1 else -18        if balance in first_seen:9            best = max(best, i - first_seen[balance])10        else:11            first_seen[balance] = i     # keep only the earliest index12    return best

Dry run on [0, 0, 1, 0, 1, 1, 1]

At i = 4, balance −1 was first seen at index 0, so indices 1 to 4 (0, 1, 0, 1) are balanced: length 4. At i = 5, balance 0 matches the seed at −1, so indices 0 to 5 are balanced: length 6. The final 1 pushes the balance to a new value, so it cannot extend anything.

Complexity. Time is O(n): one pass, O(1) average per map operation. Space is O(n) in the worst case — but the balance always lies between −n and n, so you can replace the map with a list of size 2n + 1, indexed by balance + n, if the interviewer asks for no hashing.

Edge cases

• No balanced subarray. [1, 1, 1]: balances 1, 2, 3 never repeat, so the answer stays 0.
• The whole array. [0, 1, 0, 0, 1, 1] → 6. The balance returns to 0 at the last index, and only the {0: -1} seed makes that count as length 6.
• Length 1. [0] → 0. A single element can never be balanced.
• Shortest possible answer. [0, 1] → 2.
• Every answer is even. Equal counts means an even length. If your code ever returns an odd number, it is wrong — a free sanity check.

Saying it in the interview

Follow-ups

• "Count the balanced subarrays instead." Store counts of each balance (seeded {0: 1}) and add the count on every repeat — exactly Subarray Sum Equals K with k = 0. On the lesson's example the count is 5.
• "Longest subarray whose sum is exactly k" (any integers). Same first-index map; look up balance - k instead of balance.
• "Longest subarray where 1s outnumber 0s." Now you need an earlier balance that is smaller, not equal. Because the balance moves by 1 per step, checking first_seen[balance - 1] is enough when the balance is not already positive — a neat trick worth deriving on the whiteboard.