Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Contiguous Array
• Topics: Array, Hash Table, Prefix Sum

Problem gist

Given a binary array, find the longest contiguous subarray that contains the same number of 0s and 1s.

The key constraint is that the answer must be a single continuous slice, not a subset. A brute-force check of every slice works logically, but it takes too long because there are O(n^2) possible slices. The useful observation is that “same number of zeros and ones” can be turned into a prefix-sum equality problem.

Core idea

Treat every 0 as -1 and every 1 as +1.

Now a subarray has equal numbers of 0s and 1s exactly when its transformed sum is 0. For example, [0, 1, 1, 0] becomes [-1, +1, +1, -1], and the total is 0.

Instead of recomputing sums for every possible subarray, scan once and track a running balance:

• balance decreases by 1 for a 0.
• balance increases by 1 for a 1.

If the same balance appears at two different positions, the elements between those positions must have net sum 0. That means the middle slice has equal 0s and 1s. To maximize the length, keep only the earliest index where each balance first appeared.

Deriving the algorithm

Start with balance 0 at virtual index -1. This handles answers that begin at index 0, such as [0, 1].

As the scan moves through the array:

1. Update the balance using the current value.
2. If this balance has been seen before, the subarray after its first index through the current index is balanced.
3. Update the best length using that distance.
4. If this balance is new, store the current index as its first occurrence.

The reason the first occurrence matters is simple: for a fixed current index, the farthest matching earlier balance gives the longest balanced subarray ending here. Replacing the first occurrence with a later one would only shorten future answers.

Python solution

from typing import List


class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        first_index_by_balance = {0: -1}
        balance = 0
        longest_balanced_length = 0

        for index, value in enumerate(nums):
            balance += self._balance_delta(value)

            if balance in first_index_by_balance:
                candidate_length = index - first_index_by_balance[balance]
                longest_balanced_length = max(
                    longest_balanced_length,
                    candidate_length,
                )
            else:
                # Keep the earliest index so future subarrays are as long as possible.
                first_index_by_balance[balance] = index

        return longest_balanced_length

    @staticmethod
    def _balance_delta(value: int) -> int:
        return 1 if value == 1 else -1

Complexity

The algorithm visits each array element once, so the time complexity is O(n).

The hash table can store one entry for each distinct balance. In the worst case, that is O(n) extra space.

Interview follow-ups

How would the solution change if the array contained arbitrary values and the target was equal counts of two chosen values?

Map one chosen value to +1, the other chosen value to -1, and map every unrelated value to 0. The same prefix-balance method still works because a balanced slice is exactly one where the number of first-choice values cancels the number of second-choice values.

This keeps the same O(n) time and O(n) space bounds. The main tradeoff is semantic: unrelated values can appear inside the subarray without changing the balance, so the interviewer should clarify whether those values are allowed or should break the current window.

Can this be solved with a sliding window?

Not reliably. Sliding windows work well when moving one pointer has a predictable effect, such as when all numbers are positive and a sum only grows as the right pointer moves. Here, adding a 0 decreases the balance and adding a 1 increases it, so there is no monotonic rule that tells which pointer to move.

The prefix-balance hash table is the safer optimal approach because it records every state that could become useful later. It avoids guessing where a balanced interval starts and still runs in linear time.

How would you return the actual subarray boundaries instead of only the length?

Store the best start and end indices whenever a repeated balance gives a longer candidate. If balance first appeared at previous_index, then the balanced subarray runs from previous_index + 1 through the current index.

The proof and complexity do not change. The hash table still stores the first index for each balance, and the scan still takes O(n) time. The only extra storage beyond the table is a pair of integers for the best range.

How would the idea extend to equal counts of 0, 1, and 2?

Use two relative balances instead of one. For example, track (count_1 - count_0, count_2 - count_0) as the prefix state. If the same pair appears at two indices, then the counts of 0, 1, and 2 all increased by the same amount between those indices, so the middle subarray has equal counts of all three values.

The scan is still O(n), and the hash table still stores the earliest index for each state. The space remains O(n), but the key is now a tuple rather than a single integer.