525. Contiguous Array

525

MediumArrays and HashingPrefix sum plus hash mapPrefix balance with first-seen index map

Contiguous Array

Given a binary array nums containing only 0s and 1s, return the maximum length of a contiguous subarray that contains an equal number of 0s and 1s.

Open official problem prompt ↗

In plain English

Find the longest contiguous stretch of the array holding exactly as many 1s as 0s.

Picture it like this

Track a hiker's altitude where a 1 is a step up and a 0 a step down. Whenever the hiker returns to an altitude reached earlier, the ground covered in between rose and fell equally, so net elevation change is zero.

Example

Input: nums = [0, 1, 0]
Output: 2
Why: The subarray [0,1] (indices 0..1) has one 0 and one 1; so does [1,0] (indices 1..2). Both have length 2, and no longer balanced subarray exists.

Constraints

1 <= nums.length <= 10^5nums[i] is either 0 or 1

Pattern lesson

See the pattern, then code

Prefix balance with first-seen index map

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Map 0 to -1 and 1 to +1. A subarray is balanced exactly when its running sum returns to a value it held before, because the segment between two equal prefix sums nets to zero. Remember the first index at which each prefix value appears to maximize length.

New words, made simpleKnow these before the algorithm

Prefix sum: The running total from the start up to the current index.
First-occurrence map: A dictionary storing the earliest index at which each prefix value appeared, to maximize the resulting span.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check every subarray

Quadratic; times out at n=10^5.

For each start and end, count 0s and 1s and test equality.

Time O(n^2)Space O(1)

Best choicePrefix balance + hash map

One pass finds the longest zero-net span in linear time.

Recode 0 as -1, track the running sum, and record the first index of each sum value.

Time O(n)Space O(n)

The rule we keep true

Invariant

first[c] holds the smallest index i such that the prefix sum through i equals c; the map is seeded with {0: -1} to allow a balanced prefix starting at index 0.

Why this is correct

Reasoning

If the prefix sum equals c at index a-1 and again at index b, the elements from a to b sum to zero, meaning equal numbers of +1 and -1, i.e. equal 1s and 0s. Storing only the first index of each sum guarantees that when we see the sum again we compute the longest possible span for that balance level.

The algorithm in three movesSay these aloud before coding

1Keep a running count adding +1 for 1 and -1 for 0, and a map seeded with {0: -1}

first = {0:-1}

2At each index update the count

i=0 count=-1 -> first[-1]=0

3If the count was seen before, the span since its first occurrence is balanced; update the best length

i=1 count=0 -> len = 1-(-1) = 2

4Otherwise record this index as the first occurrence of the count

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read-

2 · AskSeed the map

3 · Update statefirst={0:-1}, count=0, best=0

4 · ResultReady

Key takeaway

Prefix balance returns to 0 at index 1, so the span from index 0 to 1 has equal 0s and 1s.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Seed the map
{0: -1} lets a balanced prefix that begins at index 0 have length i-(-1) = i+1.
2
Lines 7-11Update and match
Adjust the running balance, then either extend the best span if this balance repeats or record its first occurrence.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No balanced subarray, e.g. [0,0,0] or [1] -> return 0
The whole array is balanced -> return n
Single element -> always 0
Alternating array like [0,1,0,1] -> return n

Common beginner mistakes

Forgetting to seed first with {0: -1}, which misses subarrays starting at index 0
Overwriting first[count] on repeat instead of keeping the earliest index, which shortens spans
Storing counts of prefix sums (like the divisible-by-k problem) rather than the first index; here we need max length, not a count
Treating 0 as 0 instead of -1, which breaks the zero-sum equivalence

Check your understanding

Why store the first index a prefix sum appears rather than the most recent?

Contiguous Array

Contiguous Array

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing