Skip to main content
DSA patterns

Contiguous Array

mediumPrefix sum Must-doGoogleMetaAmazon

Problem statement

You are given a binary array nums — every value in it is either 0 or 1. Find the length of the longest contiguous stretch of the array that has exactly as many 0s as 1s.

Think of nums as a timeline of flags from a rollout: 0 for a healthy check and 1 for an alert. The longest balanced stretch tells you the biggest window where good and bad signals cancelled out evenly — useful when you're hunting for the noisiest or calmest section of a long run.

Examples

Example 1

Input: nums = [0, 1]

Output: 2

Explanation: The whole array has one 0 and one 1, so the entire array is the answer.

Example 2

Input: nums = [0, 1, 0]

Output: 2

Explanation: [0, 1] (the first two values) has one of each; adding the last 0 makes it two 0s and one 1, so it can't extend further. [1, 0] (the last two) works just as well — either one gives length 2.

Example 3

Input: nums = [0, 1, 1, 1, 1, 1, 0, 0, 0]

Output: 6

Explanation: [1, 1, 1, 0, 0, 0], the last six values, has three 1s and three 0s. No longer stretch balances out.

Hints

Hint 1: Checking every possible stretch works, but how many stretches are there in an array of length n? What does that cost you as n grows?

Approach

Optimal: Hash map

Intuition

Same idea as Better — a running balance, and a stretch is valid when a balance value repeats — but store the first-seen index in a hash map keyed by the balance instead of a fixed-size array. This drops the assumption that the balance is bounded by ±n, which matters if you ever reuse the same trick on a stream where you don't know the length in advance, and it reads a little more directly: "have I seen this balance before?"

Steps

  1. Start a hash map firstSeen with {0: -1} — balance 0 "happened" one step before the array starts.
  2. Walk through nums, updating a running balance (+1 for a 1, -1 for a 0).
  3. If balance is already a key in the map, the stretch from that stored index to now is balanced — update the best length if it's longer.
  4. Otherwise, store the current index as the first time this balance was seen.
  5. Return the best length found.

Dry run

nums = [0, 1, 0], treating 0 as -1 and 1 as +1:

i value balance in map? best so far
— — 0 seeded at -1 0
0 0 -1 no → store -1: 0 0
1 1 0 yes, at -1 → length 1 - (-1) = 2 2
2 0 -1 yes, at 0 → length 2 - 0 = 2 2

Edge cases: an all-zero or all-one array never sees the balance repeat once it starts moving away from 0 (other than at the seeded start for the all-zero case at index 0), so the longest balanced stretch stays 0. A single-element array always returns 0.

Complexity

Time O(n)

Space O(n)

class Solution:
    def findMaxLength(self, nums: list[int]) -> int:
        first_seen = {0: -1}
        balance = 0
        best = 0
        for i, x in enumerate(nums):
            balance += 1 if x == 1 else -1
            if balance in first_seen:
                best = max(best, i - first_seen[balance])
            else:
                first_seen[balance] = i
        return best


if __name__ == "__main__":
    print(Solution().findMaxLength([0, 1]))
    print(Solution().findMaxLength([0, 1, 0]))
    print(Solution().findMaxLength([0, 1, 1, 1, 1, 1, 0, 0, 0]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "longest stretch with equal counts of two things" in an array
  • Idea: relabel one value as +1 and the other as -1; a running balance that repeats means the stretch between those two points is balanced
  • Cost: O(n) time, O(n) space for the hash map (or a size-bounded array if the range is known)
  • Trap: forgetting to seed balance 0 at index -1 — without it, a balanced stretch starting at index 0 is missed

Interview follow-ups

  • What if you needed the actual longest balanced subarray, not just its length?

    Store the value itself instead of throwing it away: when you find a new best length, remember the start and end index (firstSeen[balance] + 1 to i). At the end, slice nums using those saved indices. This adds O(1) extra bookkeeping per step, so the time and space complexity don't change.

  • The array is a live stream and you can't hold the whole thing in memory. What changes?

    You can still keep the running balance and the hash map of first-seen indices — that map only grows to at most 2n + 1 distinct balance values, not the full stream — so the algorithm already works incrementally on a stream. The real limit becomes how many distinct balance values you're willing to remember; if the stream runs for a very long time with a strong bias toward 0s or 1s, you can periodically drop entries for balances that are now unreachably far behind the current one.

  • What if there were three possible values instead of two (0, 1, 2) and you wanted equal counts of all three?

    The single running balance no longer captures enough information — you'd need to track two independent counts (say, count of value 1 minus count of value 0, and count of value 2 minus count of value 0) and key the hash map on the pair. The core idea survives — look for a repeated "signature" — but the signature becomes a 2D point instead of a single number, and the hash map values become 2-tuples.

Frequently asked questions

That's essentially the brute force approach in disguise — counting from scratch for every window is still O(n²) in the worst case. The balance trick avoids recomputation entirely: each index is visited once, and the running total carries all the information needed.

If you sum +1 for every 1 and -1 for every 0 across a stretch, the sum is 0 exactly when the counts of 1s and 0s match. That turns "equal counts" — a comparison between two numbers — into "sum equals zero," which is much easier to track incrementally with a single running total.

When you know the array's length ahead of time and want to avoid hash map overhead — array indexing is a simple, predictable memory access, while a hash map has bucket lookups and potential resizing. For a fixed, in-memory array this is a minor win; the hash map version is the more flexible default.

The same trick — turning a "count of A equals count of B" question into a running-sum lookup — shows up whenever you're comparing two categories of events over a window: successful vs. failed health checks, reads vs. writes in a trace, or up vs. down transitions in a status feed. Recognizing the balance-and-repeat pattern saves you from writing an O(n²) scan over logs.

Then the balance keeps growing (or shrinking) in one direction and rarely repeats, so the longest balanced stretch stays small — which is the correct answer. For example [1, 1, 1, 0] only balances over its last two elements, giving 2.