Contiguous Array (Equal Zeros and Ones): Convert Zero to Minus One, Prefix Sum Plus HashMap

• Transform – replace every 0 with -1 so equal zeros and ones become a subarray summing to zero.
• Prefix-sum repetition – a subarray sums to zero when prefix[j] == prefix[i]; the span j - i is balanced.
• HashMap – stores the first index at which each prefix-sum value appeared.
• Seed – map.put(0, -1) handles balanced subarrays starting at index 0.
• First-occurrence bookkeeping – store only the first index, never overwrite, to maximize span length.
• O(n) time, O(n) space.

What is the Contiguous Array problem?

Given a binary array of 0s and 1s, find the length of the longest contiguous subarray that contains an equal number of 0s and 1s. For example, in [0, 1, 0, 1, 1, 0], the answer is 6 (the entire array has three 0s and three 1s).

What is the clever transformation?

Replace every 0 with -1. After this, a subarray has equal 0s and 1s exactly when its elements sum to zero: each 1 contributes +1 and each former 0 contributes -1, and they cancel only when counts are equal.

Original: [0, 1, 0, 1, 1, 0]
Mapped:   [-1, 1, -1, 1, 1, -1]

Running sum: -1, 0, -1, 0, 1, 0
             ↑       ↑     ↑
          sum=-1   sum=-1  sum=0 (repeat!)

How does the prefix sum plus HashMap find the longest balanced span?

A subarray from index i+1 to j sums to zero when prefix[j] == prefix[i]. To maximize the span, store the first occurrence of each prefix-sum value. When the sum repeats at index j, the span j - firstIndex is balanced, and using the earliest first occurrence maximizes the length.

How do you implement it? (with code)

package com.bank.analytics;

import java.util.HashMap;
import java.util.Map;

public class ContiguousArray {

    public static int findMaxLength(int[] tradingDays) {
        Map<Integer, Integer> firstSeen = new HashMap<>();
        firstSeen.put(0, -1);  // seed: sum 0 first seen at virtual index -1

        int sum = 0;
        int best = 0;

        for (int i = 0; i < tradingDays.length; i++) {
            sum += (tradingDays[i] == 1) ? 1 : -1;

            if (firstSeen.containsKey(sum)) {
                best = Math.max(best, i - firstSeen.get(sum));
            } else {
                firstSeen.put(sum, i);  // store first occurrence only
            }
        }
        return best;
    }

    public static void main(String[] args) {
        // 1 = up day, 0 = down day
        int[] days = {0, 1, 0, 1, 1, 0};
        System.out.println("Longest balanced stretch: " + findMaxLength(days));
    }
}

Longest balanced stretch: 6

Why seed with sum 0 at index -1?

The seed handles balanced subarrays that start at index 0. If the running sum returns to zero at index j, the length is j - (-1) = j + 1, which correctly counts the entire prefix. Without the seed, these subarrays would be missed.

Why store first occurrence only?

This is a longest-span problem, not a count problem. Keeping the earliest index maximizes the gap between the first and current occurrence of the same prefix sum. Overwriting with a later index would shorten the potential span.

How is this different from Subarray Sum Equals K?

Both use prefix sums with a HashMap, but the bookkeeping differs.

| Problem | Goal | Map stores | Key insight |
|---|---|---|---|
| Subarray Sum Equals K | Count subarrays | Frequency of each prefix sum | Count matching prefixes |
| Contiguous Array | Longest balanced span | First index of each prefix sum | Maximize distance between matches |

What are the edge cases?

• All 0s or all 1s – no balanced subarray exists; return 0.
• Already balanced – the entire array is the answer.
• Length 1 – cannot be balanced; return 0.
• Alternating 0-1 – every even-length prefix is balanced.

What about the walkthrough with the map?

Array: [0, 1, 0, 1, 1, 0]
Map seed: {0: -1}

i=0: sum=-1, not in map → map={0:-1, -1:0}
i=1: sum=0, in map at -1 → span=1-(-1)=2, best=2
i=2: sum=-1, in map at 0 → span=2-0=2, best=2
i=3: sum=0, in map at -1 → span=3-(-1)=4, best=4
i=4: sum=1, not in map → map adds {1:4}
i=5: sum=0, in map at -1 → span=5-(-1)=6, best=6

Answer: 6

What are common interview follow-up questions?

• What about equal counts of three symbols? – Reduce to two balance conditions and use a tuple as the map key.
• Can you return the actual subarray? – Store bestStart and bestEnd when best is updated.
• What about counting balanced subarrays? – Store frequency instead of first index.