Contiguous Array

Problem Statement

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

The core trick

• Replace every 0 with -1. Now “equal 0s and 1s” means “subarray sum equals 0”.
• When the same prefix sum appears at two different positions, the subarray between those positions sums to 0.
• Initialize the map with {0: -1} to handle subarrays starting at index 0.

Examples

Input	Output	Subarray
[0,1]	2	[0,1]
[0,1,0]	2	[0,1] or [1,0]

Constraints

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

Real-World Applications

Where this pattern appears

• Network packet analysis — find the longest span where requests and responses are balanced.
• Voting record analysis — longest period where yes and no votes are equal.
• Signal balancing — longest run of a binary signal that is perfectly balanced.
• Load balancing — find time windows with equal load on two servers.

Complexity Comparison

Approach	Time	Space	Notes
Prefix Sum with 0→-1 Transform	O(n)	O(n)	Optimal solution, single pass

* n = length of the input array

The Key Transform

The problem asks for equal counts of 0 and 1. Directly comparing counts requires tracking two separate running totals. The insight is to collapse that into a single value:

Replace 0 with -1. Now each 1 contributes +1 and each 0 contributes -1. A subarray with equal 0s and 1s has net sum 0.

This reduces the problem to: find the longest subarray with sum 0, which is solved in O(n) with a prefix sum hash map — the same pattern as Subarray Sum Equals K.

The map stores the first index where each prefix sum was seen. When the same prefix sum reappears at index i, the subarray from seen[prefix]+1 to i has sum 0, so its length is i - seen[prefix]. We never update the map for a seen prefix — we always want the earliest occurrence to maximize window length.

Approach: Prefix Sum with 0→-1 Transform

★ Recommended

⏱ Time O(n) Single pass 💾 Space O(n) Hash map storage

Step-by-step Example

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

After replacing 0→-1: [-1, 1, -1, 1]

i	num	delta	prefix	seen (before)	length if match	best
—	—	—	0	{}	—	0
0	0	-1	-1	{0:-1}	—	0
1	1	+1	0	{0:-1, -1:0}	1−(−1)=2	2
2	0	-1	-1	{0:-1, -1:0}	2−0=2	2
3	1	+1	0	{0:-1, -1:0}	3−(−1)=4	4

Result: 4

Input: nums = [0,1,0]

After replacing 0→-1: [-1, 1, -1]

i	delta	prefix	seen (before)	length if match	best
—	—	0	{}	—	0
0	-1	-1	{0:-1}	—	0
1	+1	0	{0:-1, -1:0}	1−(−1)=2	2
2	-1	-1	{0:-1, -1:0}	2−0=2	2

Result: 2

Animated walkthrough

Finding maximum balanced subarray with prefix sums

Use Next or Autoplay to watch the prefix sum (with 0→-1) accumulate, the map record first-seen positions, and the window lengths calculate for nums=[0,1,0,1].

Back Autoplay Next Reset

Step 1 of 5

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function findMaxLength(nums):
    seen = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += 1 if num == 1 else -1
        if prefix in seen:
            best = max(best, i - seen[prefix])
        else:
            seen[prefix] = i
    return best

Solution Code

Python

contiguous_array_prefix_sum.py

from typing import List


def find_max_length(nums: List[int]) -> int:
    seen = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += 1 if num == 1 else -1
        if prefix in seen:
            best = max(best, i - seen[prefix])
        else:
            seen[prefix] = i
    return best

print(find_max_length([0, 1]))      # 2
print(find_max_length([0, 1, 0]))   # 2
print(find_max_length([0, 1, 0, 1]))  # 4

C++

contiguous_array_prefix_sum.cpp

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> seen;
        seen[0] = -1;
        int prefix = 0, best = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            prefix += nums[i] == 1 ? 1 : -1;
            auto it = seen.find(prefix);
            if (it != seen.end()) {
                best = max(best, i - it->second);
            } else {
                seen[prefix] = i;
            }
        }
        return best;
    }
};

Java

contiguous_array_prefix_sum.java

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

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

JavaScript

contiguous_array_prefix_sum.js

function findMaxLength(nums) {
    const seen = new Map([[0, -1]]);
    let prefix = 0, best = 0;
    for (let i = 0; i < nums.length; i++) {
        prefix += nums[i] === 1 ? 1 : -1;
        if (seen.has(prefix)) {
            best = Math.max(best, i - seen.get(prefix));
        } else {
            seen.set(prefix, i);
        }
    }
    return best;
}

Rust

contiguous_array_prefix_sum.rs

use std::collections::HashMap;

impl Solution {
    pub fn find_max_length(nums: Vec<i32>) -> i32 {
        let mut seen: HashMap<i32, i32> = HashMap::new();
        seen.insert(0, -1);
        let mut prefix = 0;
        let mut best = 0;
        for (i, &num) in nums.iter().enumerate() {
            prefix += if num == 1 { 1 } else { -1 };
            if let Some(&first) = seen.get(&prefix) {
                best = best.max(i as i32 - first);
            } else {
                seen.insert(prefix, i as i32);
            }
        }
        best
    }
}

Go

contiguous_array_prefix_sum.go

func findMaxLength(nums []int) int {
    seen := map[int]int{0: -1}
    prefix, best := 0, 0
    for i, num := range nums {
        if num == 1 {
            prefix++
        } else {
            prefix--
        }
        if first, ok := seen[prefix]; ok {
            if i-first > best {
                best = i - first
            }
        } else {
            seen[prefix] = i
        }
    }
    return best
}

Common Mistakes

Watch for these pitfalls

• Not initializing the map with {0: -1} — without this, subarrays starting at index 0 are never detected.
• Updating seen[prefix] when the key already exists — you want the first (earliest) occurrence to maximize the window length. Never overwrite an existing entry.
• Forgetting to replace 0 with -1 — adding 0 to the prefix sum does nothing, so the prefix never changes when a 0 is encountered, breaking the algorithm entirely.

Related Problems

• Subarray Sum Equals K ↗ Medium #560
• Two Sum ↗ Easy #1
• Longest Consecutive Sequence ↗ Medium #128

Interview Tips

Key points to discuss

• State the 0→-1 substitution explicitly — this is the core insight that transforms the problem into a prefix sum problem. Say it out loud before writing code.
• Why not update the map when we see a duplicate? — because the first occurrence gives the longest possible window. Updating would shrink the answer.
• Works in O(n) with a single pass — there is no better asymptotic solution since every element must be read at least once.
• Edge cases: an all-zeros or all-ones array returns 0. An array of length 1 always returns 0. The algorithm handles both correctly.

← Previous
#502 IPO Next
#530 Minimum Absolute Difference in BST →