Contiguous Array

You are given a binary array nums (every element is 0 or 1). Find the longest contiguous subarray that contains the same number of 0s as 1s, and return its length.

A subarray is a run of neighbouring elements taken without gaps, for example nums[2..5]. It is called balanced when the count of zeros inside it equals the count of ones, which also means its length is always even. If the array has no balanced subarray at all (for instance when every element is the same), return 0.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Hashing & Counting · problem 10 of 169

Start simple

For each start index, extend to the right while keeping counts of 0s and 1s, recording the longest balanced stretch: O(n²) time, O(1) space.

The key idea

Replace every 0 with -1. A subarray now has equal numbers of 0s and 1s exactly when its elements add up to zero.

Let prefix[j] be the running total after index j. The sum of the subarray from i + 1 to j is prefix[j] - prefix[i], so it is balanced exactly when prefix[i] == prefix[j]. For each j, the longest balanced subarray ending there starts right after the earliest index with the same running total.

So scan once, keeping a hash map from running total to the first index where it occurred. Seed it with {0: -1} so that a balanced prefix starting at index 0 is measured correctly. At each index, if the total was seen before, the candidate length is j - first[total]; otherwise record j as its first occurrence. Never overwrite an existing entry, since an earlier start always gives a longer subarray.

Complexity

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

Python

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        first_seen = {0: -1}  # running balance -> earliest index where it occurred
        balance = best = 0
        for i, x in enumerate(nums):
            balance += 1 if x == 1 else -1
            if balance in first_seen:
                best = max(best, i - first_seen[balance])  # the stretch in between sums to 0
            else:
                first_seen[balance] = i
        return best

JavaScript

var findMaxLength = function(nums) {
  const firstSeen = new Map([[0, -1]]); // running balance -> earliest index where it occurred
  let balance = 0, best = 0;
  for (let i = 0; i < nums.length; i++) {
    balance += nums[i] === 1 ? 1 : -1;
    if (firstSeen.has(balance)) {
      best = Math.max(best, i - firstSeen.get(balance)); // the stretch in between sums to 0
    } else {
      firstSeen.set(balance, i);
    }
  }
  return best;
};

What the interviewer is checking

This checks whether you can reframe a counting condition as a zero-sum subarray and apply the prefix-sum plus first-occurrence hash map pattern.

Mistakes to avoid

• Forgetting the initial entry {0: -1}, which misses balanced subarrays that start at index 0.
• Updating the stored index on every repeat, which keeps the latest occurrence and shortens answers.
• Treating 0 as 0 instead of -1, so the sum no longer measures the balance.

Follow-ups to expect

• Return the subarray's start and end, not just length. (Track indices with best.)
• Longest subarray whose sum equals k. (Same map, look up prefix − k.)
• Count all balanced subarrays. (Map prefix sum to frequency.)

In real software

Finding the longest window where two event types balance out, such as equal buys and sells in a trade log or equal ups and downs in a sensor trace, uses the same running-balance hash map.

Practice next