Command Palette

Search for a command to run...

Hectal
Problem 5.5 · Prefix SumMedium

Contiguous Array

PatternPrefix Sum + Hash Map

What it teaches: Turn "equal 0s and 1s" into "sum zero" by counting 0 as −1, then find the longest zero-sum subarray with first-seen indexes.

Practise it on judges as “Contiguous Array”.

The problem

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

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 1 ≤ nums.length ≤ 10⁵
  • nums[i] is 0 or 1

Pattern clues in the wording

  • → "Equal number of A and B" → map them to −1 and +1 and look for sum 0
  • → Longest subarray → remember the first index of each prefix sum

These clues point to Prefix Sum + Hash Map: Count subarrays with a target sum by remembering how often each running total has appeared.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int findMaxLength(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [0,1]
2
2
nums = [0,1,0]
2
3
nums = [0,0,1,0,0,0,1,1]
6

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: −1/+1 prefix sums with first-seen indexes · O(n)
1

Optimal: −1/+1 prefix sums with first-seen indexes

Time O(n) Space O(n)

Running sum adds +1 for a 1 and −1 for a 0. If sum at index j was first seen at index i, then nums[i+1..j] is balanced, with length j − i. Seed the map with sum 0 at index −1.

▶ Dry run: Equal prefix sums enclose a balanced runnums = [0, 1, 0]
0
0
1
1
0
2

first index of sum(map)

0 → -1

State(vars)

sum = 0best = 0

Step 1/4Seed: sum 0 at index −1.

Approach 1
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int sum = 0, best = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i] == 1 ? 1 : -1;
            Integer j = first.get(sum);
            if (j != null) best = Math.max(best, i - j);
            else first.put(sum, i);          // keep only the first index
        }
        return best;
    }
}

Verdict: One pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No balanced subarray → 0
  • The whole array is balanced
  • All zeros

Mistakes people make

  • Overwriting the first-seen index with later ones (shortens the answer).
  • Seeding with index 0 instead of −1.

Interview

Follow-up questions

What if you need the longest subarray where 1s exceed 0s?