Contiguous Array

Practice Link

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

Brute Force#

Fix a start index i and expand with end index j, counting zeros and ones. Whenever the counts are equal, update the max length. Correct but O(n²) — TLEs on large inputs.

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

        for(int i = 0; i < n; i++){
            int zeros = 0, ones = 0;
            for(int j = i; j < n; j++){
                if(nums[j] == 0) zeros++;
                else             ones++;
                if(zeros == ones)
                    maxLen = max(maxLen, j - i + 1);
            }
        }
        return maxLen;
    }
};

Time Complexity: O(n²)

Space Complexity: O(1)

Optimal — Prefix Sum#

Key insight: replace every 0 with -1. Now equal counts of 0s and 1s means the subarray sums to 0. The problem becomes "longest subarray with sum 0" — identical in structure to Longest Subarray with Sum K.

Use a prefix-sum hash map that stores the first index at which each running sum was seen. When the same prefix sum repeats at index i, the subarray between the two occurrences sums to 0 (equal 0s and 1s). Seeding firstSeen[0] = -1 handles subarrays that start at index 0.

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

        unordered_map<int,int> firstSeen;
        firstSeen[0] = -1;   // seed: prefix sum 0 "occurred" before the array

        int prefixSum = 0, maxLen = 0;

        for(int i = 0; i < n; i++){
            prefixSum += (nums[i] == 0 ? -1 : 1);   // 0 → -1, 1 → +1

            if(firstSeen.find(prefixSum) != firstSeen.end())
                maxLen = max(maxLen, i - firstSeen[prefixSum]);
            else
                firstSeen[prefixSum] = i;   // store only first occurrence
        }
        return maxLen;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Why only the first occurrence? If the same prefix sum appears at indices j and j' with j < j', the subarray nums[j+1..i] is longer than nums[j'+1..i]. Storing only the first keeps the maximum possible window.

Follow-up: Replace the Hash Map with an Array#

If you knew the range of the running sum in advance, how could you replace the hash map to achieve even faster execution?

For a binary array of length n, every element contributes either -1 or +1 to the running sum. The prefix sum is therefore bounded:

-n  ≤  prefixSum  ≤  +n

That's only 2n + 1 distinct values — a fixed, known range. We can allocate a plain int array of that size and use prefixSum + n as the index, replacing hash-map lookups with direct array access.

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

        // index range: [-n, +n] → offset by n to get [0, 2n]
        vector<int> firstSeen(2 * n + 1, INT_MIN);
        firstSeen[n] = -1;   // prefix sum 0 maps to slot n (explained below)

        int prefixSum = 0, maxLen = 0;

        for(int i = 0; i < n; i++){
            prefixSum += (nums[i] == 0 ? -1 : 1);

            int idx = prefixSum + n;
            if(firstSeen[idx] != INT_MIN)
                maxLen = max(maxLen, i - firstSeen[idx]);
            else
                firstSeen[idx] = i;
        }
        return maxLen;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Why does prefix sum 0 map to slot n?

The index formula is prefixSum + n. When prefixSum = 0:

index = 0 + n = n

The offset +n shifts the entire range [-n, +n] into valid array indices [0, 2n]. Zero lands exactly in the middle:

prefixSum:  -n  ...  -1   0   1  ...  +n
index:       0  ...  n-1  n  n+1 ...  2n
                          ↑
                     slot n = "prefix sum is zero"

Setting firstSeen[n] = -1 means "prefix sum 0 was first seen at index −1" — before the array starts. This seeds the empty prefix so that when prefixSum returns to 0 at some index i, the length i − (−1) = i + 1 correctly counts the entire balanced prefix without any special-case branch.

Worked example — nums = [0, 1, 0, 1] (0 → −1, 1 → +1):

Without the seed, both hits at slot n (i=1 and i=3) would be skipped and the answer would be 0.

Trade-off vs hash map:

The array version avoids hashing overhead and hash collisions entirely, making it faster in practice even though both are O(n) asymptotically.