Contiguous Array LeetCode Solution (Medium) (2026)

Approach Summary

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

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

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

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;
}

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;
}

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

Algorithmic Pattern

Master the Prefix Sum Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Prefix Sum pattern.

Framework: Prefix Sum • Interview Prep: Tested at FAANG • Explore all Prefix Sum problems & invariants →

How to Recognize This Pattern

Equal number of 0s and 1s in subarray

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Frequently Asked Questions

What is the optimal time and space complexity for Contiguous Array?

The optimal solution for Contiguous Array achieves O(n) runtime complexity and requires O(n) auxiliary space. A single pass with O(1) map operations — O(n) time. The map stores up to n distinct running sums — O(n) space.

How do I identify that Contiguous Array requires the Prefix Sum pattern?

In technical interviews, look for key problem signals: Equal number of 0s and 1s in subarray. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Prefix Sum strategy.

What critical edge cases must be handled in Contiguous Array?

Essential edge cases to verify include: 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. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Contiguous Array?

Contiguous Array is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Facebook.

Contiguous Array LeetCode Solution