What is the brute force approach and complexity for Contiguous Array?

Fix each start, grow the end with a running balance, check balance == 0 with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Contiguous Array?

Same balance seen before ⇒ the part in between is balanced; store the first index of each balance with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Contiguous Array?

Look for key signals in the prompt: "contiguous subarray" indicates A range [l..r] → think window or prefix sums.; "same number of 0s and 1s" indicates Two counts that must cancel → map 0 → −1, 1 → +1 and look for sum 0.; "longest" indicates Pair each end with the **earliest** matching prefix → store the first index, not a count..

Contiguous Array

Medium·LeetCode #525Basic Anchor

LeetCode

Jump:

30-Second Mental ModelPrefix Sum (balance) + first-index hash map

Complexity:O(N²)→O(N)

Key Insight

Keep a running balance from index 0. If the balance at index i equals the balance at an earlier index j, then everything in nums[j+1..i] added up to 0, so it is balanced. Store the first index where each balance appeared (with balance 0 at index −1). At each i, the longest balanced subarray ending at i has length i − first[balance].

Core Validity Invariant

nums[j+1..i] has equal 0s and 1s exactly when the running balance at j equals the running balance at i.

Problem

You are given an array nums that holds only 0s and 1s.

Find the longest contiguous subarray that has the same number of 0s and 1s, and return its length. If there is no such subarray, return 0.

Input

A binary array nums (every value is 0 or 1).

Output

The length of the longest subarray with equally many 0s and 1s.

Example 1

Input: nums = [0, 1]

Output: 2

The whole array has one 0 and one 1.

Example 2

Input: nums = [0, 1, 0]

Output: 2

[0, 1] or [1, 0] both work. The whole array has two 0s and one 1, so it does not.

Example 3

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

Output: 6

[1, 1, 1, 0, 0, 0] (indices 3..8) has three of each. No longer subarray is balanced.

Constraints

• 1 ≤ nums.length ≤ 10^5
• nums[i] is either 0 or 1

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
What single number could tell me "this part has as many 0s as 1s"?
2.
If I count a 1 as +1 and a 0 as −1, what is the sum of a balanced subarray?
3.
If the running total is the same at two different indices, what happened in between?
4.
I want the longest answer. For a fixed end, which earlier index should I pair it with?
5.
How do I handle a balanced subarray that starts right at index 0?

Brute force approach

Idea

For every start, walk the end to the right. Keep a running balance (+1 for a 1, −1 for a 0). Whenever the balance is 0, the subarray has equal counts, so update the best length.

Thinking process

1
A subarray is fixed by its start and its end. Try every pair.
2
Do not recount the subarray from scratch: for a fixed start, add one element at a time.
3
Instead of two counters, one number is enough: +1 for a 1 and −1 for a 0. Equal counts means this number is 0.
4
Unlike a sum of 0s and 1s, the balance can go up and down, so we cannot stop early. We must walk every end.

Code & Implementation

brute.cpp

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int best = 0;

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            int balance = 0;   // (#1s) - (#0s) in nums[start..end]
            for (int end = start; end < n; end++) {
                balance += (nums[end] == 1) ? 1 : -1;
                // Balance 0 means the same number of 0s and 1s.
                if (balance == 0) best = max(best, end - start + 1);
            }
        }
        return best;
    }
};

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int best = 0;

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            int balance = 0; // (#1s) - (#0s) in nums[start..end]
            for (int end = start; end < n; end++) {
                balance += (nums[end] == 1) ? 1 : -1;
                // Balance 0 means the same number of 0s and 1s.
                if (balance == 0) {
                    best = Math.max(best, end - start + 1);
                }
            }
        }
        return best;
    }
}

class Solution:
    def findMaxLength(self, nums: list[int]) -> int:
        n = len(nums)
        best = 0

        # Try every start, then grow the end one step at a time.
        for start in range(n):
            balance = 0
            for end in range(start, n):
                balance += 1 if nums[end] == 1 else -1
                if balance == 0:
                    best = max(best, end - start + 1)
        return best

export function findMaxLength(nums: number[]): number {
    const n = nums.length;
    let best = 0;

    // Try every start, then grow the end one step at a time.
    for (let start = 0; start < n; start++) {
        let balance = 0; // (#1s) - (#0s) in nums[start..end]
        for (let end = start; end < n; end++) {
            balance += (nums[end] === 1) ? 1 : -1;
            // Balance 0 means the same number of 0s and 1s.
            if (balance === 0) {
                best = Math.max(best, end - start + 1);
            }
        }
    }
    return best;
}

Complexity

Time O(N²)Space O(1)

About n²/2 (start, end) pairs. With n = 10^5 that is 5·10^9 steps — far too slow. If you also recount each subarray from scratch it becomes O(N³).

Optimized approach

Idea

Start from brute force

Brute force fixes a start, walks every end, and keeps a running balance. It stops to record the length whenever the balance is 0.

Find the repeated work

For a fixed end, it tries every start one by one. But the balance of nums[j+1..i] is just (running balance at i) − (running balance at j). We already passed index j earlier — we only need to remember what its running balance was.

Define the state — what variables do I need?

balance: (#1s − #0s) in nums[0..i]. It is the prefix sum after turning 0 into −1.
first: Map from a balance value to the first index where the running balance had that value. Starts as {0: −1}.
best: Length of the longest balanced subarray found so far.

Define validity

nums[j+1..i] has equal 0s and 1s exactly when the running balance at j equals the running balance at i.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

first[0] = −1

Before reading anything, the balance is 0. Pretending it was stored at index −1 lets a subarray that starts at index 0 have length i − (−1) = i + 1.

Every index i

balance += (nums[i] == 1 ? +1 : −1)

Turning 0s into −1 makes "equal counts" the same as "sum is 0".

balance is already in first

best = max(best, i − first[balance])

The part after first[balance] up to i added nothing to the balance, so it is balanced. The first index gives the longest such part. We do not update the map here.

balance is new

first[balance] = i

Remember the earliest place this balance showed up. Any later index with the same balance will pair with it to get the longest subarray.

What does the current window add to the answer?

At index i, the longest balanced subarray that ends at i has length i − first[balance] (if that balance was seen). The answer is the largest of these over all i.

Code & Implementation

optimal.cpp

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // first[b] = the FIRST index where the running balance was b.
        unordered_map<int, int> first;
        first[0] = -1;            // balance 0 "before" index 0: lets a subarray start at 0

        int balance = 0, best = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            balance += (nums[i] == 1) ? 1 : -1;   // 1 -> +1, 0 -> -1

            auto it = first.find(balance);
            if (it != first.end()) {
                // Same balance at it->second and at i, so nums[it->second+1 .. i]
                // has as many 1s as 0s. The earliest index gives the longest one.
                best = max(best, i - it->second);
            } else {
                first[balance] = i;   // only store the first time; never overwrite
            }
        }
        return best;
    }
};

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findMaxLength(int[] nums) {
        // first[b] = the FIRST index where the running balance was b.
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1); // balance 0 "before" index 0: lets a subarray start at 0

        int balance = 0, best = 0;
        for (int i = 0; i < nums.length; i++) {
            balance += (nums[i] == 1) ? 1 : -1;

            if (first.containsKey(balance)) {
                // Same balance at first.get(balance) and at i, so nums[first.get(balance)+1 .. i]
                // has as many 1s as 0s. The earliest index gives the longest one.
                best = Math.max(best, i - first.get(balance));
            } else {
                first.put(balance, i); // only store the first time; never overwrite
            }
        }
        return best;
    }
}

class Solution:
    def findMaxLength(self, nums: list[int]) -> int:
        # first[b] = the FIRST index where the running balance was b.
        first = {0: -1}

        balance = 0
        best = 0
        for i, x in enumerate(nums):
            balance += 1 if x == 1 else -1
            if balance in first:
                best = max(best, i - first[balance])
            else:
                first[balance] = i
        return best

export function findMaxLength(nums: number[]): number {
    // first[b] = the FIRST index where the running balance was b.
    const first = new Map<number, number>();
    first.set(0, -1);

    let balance = 0;
    let best = 0;
    for (let i = 0; i < nums.length; i++) {
        balance += (nums[i] === 1) ? 1 : -1;

        if (first.has(balance)) {
            best = Math.max(best, i - first.get(balance)!);
        } else {
            first.set(balance, i);
        }
    }
    return best;
}

Complexity

Time O(N)Space O(N)

The balance always stays between −n and n, so instead of a hash map you can use a plain array of size 2n + 1 with an offset of n (index balance + n), filled with a "not seen" marker. Same O(N) time and space, but faster in practice.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Fix each start, grow the end with a running balance, check balance == 0	O(N²)	O(1)
Optimal	Same balance seen before ⇒ the part in between is balanced; store the first index of each balance	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous subarray”A range [l..r] → think window or prefix sums.
“same number of 0s and 1s”Two counts that must cancel → map 0 → −1, 1 → +1 and look for sum 0.
“longest”Pair each end with the **earliest** matching prefix → store the first index, not a count.

Contiguous range+two kinds of values must balance+longest→Prefix Sum (balance) + first-index hash map

This is the anchor of the Prefix state / balance sub-pattern. The new move compared with Exact sum + hash map is the transform: turn the array into +1/−1 so that "balanced" becomes "sum 0", which becomes "same prefix value seen before". And because we want the longest subarray (not a count), the map stores the first index of each balance instead of how many times it appeared. The next questions keep this idea but change the state: a bitmask of parities (vowels in even counts), or a balance that must be greater than 0 (well-performing interval).

Don't make this mistake

Trying a sliding window

This is a pattern-confusion trap. A window needs a rule like "if it is broken, shrinking can fix it". Here there is none: a window with too many 1s might become balanced by adding more 0s on the right, not by removing from the left. And removing a 0 from the left makes it worse. So you cannot tell when to shrink. "Equal counts" is an exact-sum condition (sum = 0 after the ±1 transform), which is a prefix-sum job.

Overwriting the stored index

✗ first[balance] = i; // every time

✓ if (!first.count(balance)) first[balance] = i;

If you update the map every time, it keeps the last index of each balance. Then i − first[balance] pairs the end with the closest start instead of the farthest, and you get shorter answers. On [0, 1, 0, 1] it returns 2 instead of 4.

Forgetting the −1 seed

✗ unordered_map<int, int> first; // empty

✓ first[0] = -1;

Without it, a balanced subarray that starts at index 0 is never found. On [0, 1] the balance goes −1, 0 and 0 was never stored, so the answer comes out 0 instead of 2.

Seeding with 0 instead of −1

✗ first[0] = 0;

✓ first[0] = -1;

Length is i − first[balance]. The empty prefix ends before index 0, i.e. at −1. Seeding 0 makes every subarray that starts at index 0 one too short.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture