Problem statement

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

Example 1

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

Example 2

Input: nums = [0,1,0]
Output: 2
Explanation: Either [0,1] or [1,0].

Example 3

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

Constraints

• 1 <= nums.length <= 40
• nums[i] is either 0 or 1.

Hints for Contiguous Array

1. Hint 1

   Rewrite each 0 as -1. Then the question becomes: what is the longest subarray summing to zero?

2. Hint 2

   Track the running sum. Two positions with the same running sum bracket a zero-sum stretch.

3. Hint 3

   Store the first index at which each running sum appears — that maximises the span.

How to solve Contiguous Array

Treat 0 as -1; a balanced subarray is then a zero-sum subarray, which sits between two positions with equal running sums. Remember the first index of each running sum to maximise the span.

Approach

1. Start with first = {0: -1} and balance = 0.
2. For each i, add +1 for a 1 and -1 for a 0.
3. If balance was seen before at j, the subarray (j, i] is balanced — update the best with i - j; otherwise record first[balance] = i.

Why it works

The sum of (j, i] equals balance[i] - balance[j], which is zero exactly when the two running sums match. Keeping the earliest index for each value gives the longest possible subarray ending at i.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The seed {0: -1} is what allows a balanced prefix starting at index 0 to be measured.
• Overwriting first[balance] with a later index shortens later matches.

Reference solution

Python

def findMaxLength(nums) -> int:
    first = {0: -1}
    balance = 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

Java

public static int findMaxLength(int[] nums) {
    Map<Integer, Integer> firstAt = new HashMap<>();
    firstAt.put(0, -1);
    int balance = 0, best = 0;
    for (int i = 0; i < nums.length; i++) {
        balance += nums[i] == 1 ? 1 : -1;
        Integer seen = firstAt.get(balance);
        if (seen != null) {
            best = Math.max(best, i - seen);
        } else {
            firstAt.put(balance, i);
        }
    }
    return best;
}

C++

int findMaxLength(vector<int>& nums) {
    unordered_map<int, int> firstAt;
    firstAt[0] = -1;
    int balance = 0, best = 0;
    for (int i = 0; i < (int) nums.size(); i++) {
        balance += nums[i] == 1 ? 1 : -1;
        if (firstAt.count(balance)) {
            best = max(best, i - firstAt[balance]);
        } else {
            firstAt[balance] = i;
        }
    }
    return best;
}

JavaScript

var findMaxLength = function(nums) {
    const firstAt = new Map();
    firstAt.set(0, -1);
    let balance = 0, best = 0;
    for (let i = 0; i < nums.length; i++) {
        balance += nums[i] === 1 ? 1 : -1;
        if (firstAt.has(balance)) {
            const len = i - firstAt.get(balance);
            if (len > best) best = len;
        } else {
            firstAt.set(balance, i);
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium