Contiguous Array

Approach Summary

Replace 0s with -1s. Find longest subarray with sum 0 using prefix sum + hash map. Same as finding two equal prefix sums.

Full Solution & Approach

Replace every 0 with -1. Now the problem becomes finding the longest subarray whose sum is 0, because a balanced run of 0s and 1s contributes exactly zero. Track a running sum and record the first index where each running-sum value appears in a map. When the same running sum appears again at index i, the subarray between the two occurrences sums to 0 — update the best length with i - first_seen[running]. Only store the first occurrence of each sum so the span is maximized. The map is seeded with {0: -1} so a balanced subarray starting at index 0 is counted correctly. The core trick — transform a binary-balance question into a prefix-sum-equals-0 question — is the same reduction used in longest-subarray-with-equal-0s-and-1s variants across multiple platforms.

A single pass with O(1) map operations — O(n) time. The map stores up to n distinct running sums — O(n) space.

Solution Code

Solution

def find_max_length(nums: list[int]) -> int:
    first_seen = {0: -1}
    running = 0
    best = 0
    for i, n in enumerate(nums):
        running += 1 if n == 1 else -1
        if running in first_seen:
            best = max(best, i - first_seen[running])
        else:
            first_seen[running] = i
    return best

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

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

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

Edge Cases to Watch

No balanced subarray — returns 0
Balanced subarray starting at index 0 — the {0: -1} seed handles it
All zeros or all ones — longest balanced run is 0
An odd-length array cannot have a balanced full run but can contain one

How to Recognize This Pattern

Equal number of 0s and 1s in subarray

Complexity Analysis

Time Complexity

O(n)

Space Complexity