Contiguous Array

medium array hash map prefix sum

Problem

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

Inputnums = [0, 1, 0, 0, 1, 1, 0]

Output6

Indices [0..5] have three 0s and three 1s.

nums (0s and 1s, comma-separated)

def find_max_length(nums):
    seen = {0: -1}
    s = 0
    best = 0
    for i, x in enumerate(nums):
        s += 1 if x == 1 else -1
        if s in seen:
            best = max(best, i - seen[s])
        else:
            seen[s] = i
    return best

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

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

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

Explanation

We want the longest stretch with equal 0s and 1s. The neat trick is to treat each 1 as +1 and each 0 as -1, and keep a running sum s. A balanced stretch is exactly one where the running sum is the same at both ends.

Why? If s has the same value at index j and at a later index i, then everything in between added up to zero, meaning equal numbers of +1 and -1 — equal 0s and 1s.

So we store the first index where each sum value appears in a map seen. When we meet a sum we have seen before, the distance i - seen[s] is a balanced length, and we keep the largest. We seed seen with {0: -1} so a balance starting at index 0 measures correctly.

Example: nums = [0,1,0,0,1,1,0]. The running sums dip and rise, and the sum value at index 5 matches one seen earlier near the start, giving a balanced span of length 6.

We only record the first occurrence of each sum (to maximize length) and never overwrite it, so one pass is enough.

Time: O(n) Space: O(n)