DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Contiguous Array

mediumPrefix sum Must-do

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

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]))

Follow-up questions

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.

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.

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.

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

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.