How do you approach Contiguous Array (Equal Zeros and Ones)?

Treat 0 as -1 and 1 as +1. Now 'equal counts' becomes 'sum is zero'.

What is the time complexity of Contiguous Array (Equal Zeros and Ones)?

Time complexity: O(n). Space complexity: O(n) for the map of first-seen indices..

What are common mistakes on Contiguous Array (Equal Zeros and Ones)?

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0. Counting the current prefix before checking for its complement, so a zero-sum range matches itself. Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.

gitGood.dev

← Back to problems

Contiguous Array (Equal Zeros and Ones)

MediumAlgorithms

Description

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

Return 0 if no such subarray exists.

Example 1

Input: nums = [0,1]

Output: 2

Example 2

Input: nums = [0,1,0]

Output: 2

Example 3

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

Output: 6

Constraints

- 1 <= nums.length <= 10^5 - nums[i] is either 0 or 1 - An O(n^2) scan over all subarrays is too slow at the upper bound.

Contiguous Array (Equal Zeros and Ones): approach, complexity and pitfalls

A medium prefix sum problem, graded against 6 test cases (3 of them hidden).

The pattern: Prefix Sum

Precomputed cumulative totals so any range query becomes one subtraction.

Reach for it when you see: Repeated range-sum queries, or counting subarrays that sum to a target.

If you are stuck

Show the 3-step hint ladder

Treat 0 as -1 and 1 as +1. Now 'equal counts' becomes 'sum is zero'.
A subarray sums to zero exactly when its two boundary prefix sums are equal. Record the FIRST index at which each prefix value appeared.
Seed the map with prefix 0 at index -1, so a balanced subarray starting at index 0 measures its length correctly.

The optimal approach

Show the approach: Re-encode, then look for repeats

Counting two things at once is awkward. Map `0` to `-1` and `1` to `+1` and the condition collapses: a subarray has equal counts exactly when it sums to zero.

A subarray sums to zero when the running prefix has the same value at both ends. So sweep once, and the first time you see a prefix value, record its index; every later re-appearance of that value marks a balanced subarray, whose length is the index distance. Keeping only the first index for each value is what maximizes the length - a later occurrence would only ever produce a shorter span.

The seed `prefix 0 -> index -1` handles subarrays that start at index 0. Without it, `[0,1]` returns 0 instead of 2, which is the classic off-by-one in this problem.

Time: O(n)
Space: O(n) for the map of first-seen indices.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Prefix Sum mistakes

These apply to the pattern as a whole, not just this problem.

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0.
Counting the current prefix before checking for its complement, so a zero-sum range matches itself.
Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.

← Back to problems

Contiguous Array (Equal Zeros and Ones)

MediumAlgorithms

Description

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

Return 0 if no such subarray exists.

Example 1

Input: nums = [0,1]

Output: 2

Example 2

Input: nums = [0,1,0]

Output: 2

Example 3

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

Output: 6

Constraints

- 1 <= nums.length <= 10^5 - nums[i] is either 0 or 1 - An O(n^2) scan over all subarrays is too slow at the upper bound.

Contiguous Array (Equal Zeros and Ones): approach, complexity and pitfalls

A medium prefix sum problem, graded against 6 test cases (3 of them hidden).

The pattern: Prefix Sum

Precomputed cumulative totals so any range query becomes one subtraction.

Reach for it when you see: Repeated range-sum queries, or counting subarrays that sum to a target.

If you are stuck

Show the 3-step hint ladder

Treat 0 as -1 and 1 as +1. Now 'equal counts' becomes 'sum is zero'.
A subarray sums to zero exactly when its two boundary prefix sums are equal. Record the FIRST index at which each prefix value appeared.
Seed the map with prefix 0 at index -1, so a balanced subarray starting at index 0 measures its length correctly.

The optimal approach

Show the approach: Re-encode, then look for repeats

Counting two things at once is awkward. Map `0` to `-1` and `1` to `+1` and the condition collapses: a subarray has equal counts exactly when it sums to zero.

The seed `prefix 0 -> index -1` handles subarrays that start at index 0. Without it, `[0,1]` returns 0 instead of 2, which is the classic off-by-one in this problem.

Time: O(n)
Space: O(n) for the map of first-seen indices.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Prefix Sum mistakes

These apply to the pattern as a whole, not just this problem.

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0.
Counting the current prefix before checking for its complement, so a zero-sum range matches itself.
Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.