Contiguous Array (Longest Subarray with Equal Zeros and Ones)

• Transform: treat each 0 as -1 and each 1 as +1.
• A subarray with equal zeros and ones has a transformed sum of zero.
• A zero-sum subarray = two equal prefix sums, so find the longest distance between them.
• Store only the first occurrence of each prefix value in a hash map.
• Seed with {0: -1} for subarrays starting at index 0.
• Time is O(N) and space is O(N).

What is the Contiguous Array (Equal Zeros and Ones) problem?

Given a binary array of 0s and 1s, find the length of the longest contiguous subarray containing an equal number of zeros and ones. This is LeetCode 525.

For example, given [0, 1, 0, 1, 1, 0, 0], the longest balanced subarray has length 6: [1, 0, 1, 1, 0, 0] from index 1 to 6.

Why transform 0 to -1?

With the substitution 0 becomes -1 and 1 stays +1, a subarray with equal zeros and ones has a sum of exactly zero. This turns a counting problem into a zero-sum prefix problem, unlocking the prefix-sum technique.

// Original: [0, 1, 0, 1]
// Transformed: [-1, 1, -1, 1]
// Sum = 0, meaning equal zeros and ones

How does the first-occurrence map work?

package com.bank.service;

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

public class ContiguousArrayService {

    /**
     * Finds the longest break-even trading stretch.
     * Used by the National Bank of India risk analysis team.
     */
    public static int findMaxLength(int[] outcomes) {
        Map<Integer, Integer> firstOccurrence = new HashMap<>();
        firstOccurrence.put(0, -1); // Seed: prefix 0 at index -1

        int prefix = 0;
        int maxLength = 0;

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

            if (firstOccurrence.containsKey(prefix)) {
                int length = i - firstOccurrence.get(prefix);
                maxLength = Math.max(maxLength, length);
            } else {
                firstOccurrence.put(prefix, i);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] outcomes = {0, 1, 0, 1, 1, 0, 0};
        System.out.println("Longest break-even stretch: "
            + findMaxLength(outcomes) + " days");
    }
}

javac -d out com/bank/service/ContiguousArrayService.java
java -cp out com.bank.service.ContiguousArrayService

Longest break-even stretch: 6 days

Why store only the first occurrence?

We want the longest span between two equal prefix values. If we overwrote the stored index with a later one, we would shorten the possible span. The earliest occurrence maximizes the distance to any future matching prefix.

// WRONG: overwrite shortens the span
firstOccurrence.put(prefix, i); // Always overwrites

// CORRECT: store only the first time
if (!firstOccurrence.containsKey(prefix)) {
    firstOccurrence.put(prefix, i); // Only the first occurrence
}

Why seed with {0: -1}?

The seed represents the empty prefix before the array starts. If a balanced subarray begins at index 0, the prefix sum returns to 0 at some later index i. The length is i - (-1) = i + 1, which correctly counts all elements from 0 to i.

What are the edge cases?

Several edge cases require attention.

• All zeros or all ones: no balanced subarray exists, return 0.
• Two elements [0, 1] or [1, 0]: the answer is 2.
• Entire array is balanced: the answer is the full length.
• Empty array: the answer is 0.

package com.bank.core;

public class ContiguousArrayEdgeCases {
    public static void main(String[] args) {
        System.out.println(findMax(new int[]{1, 1, 1}));     // 0
        System.out.println(findMax(new int[]{0, 1}));         // 2
        System.out.println(findMax(new int[]{0, 1, 0, 1}));   // 4
    }

    static int findMax(int[] arr) {
        java.util.Map<Integer, Integer> map = new java.util.HashMap<>();
        map.put(0, -1); int pre = 0, best = 0;
        for (int i = 0; i < arr.length; i++) {
            pre += arr[i] == 1 ? 1 : -1;
            if (map.containsKey(pre)) best = Math.max(best, i - map.get(pre));
            else map.put(pre, i);
        }
        return best;
    }
}

0
2
4

What is the time and space complexity?

Time is O(N): one pass with O(1) map operations per element. Space is O(N) for the hash map. The prefix values range from -N to +N, so an offset array of size 2N+1 could replace the map for slightly better performance.

How is this related to other prefix-sum problems?

This is the "longest subarray" variant of the prefix-sum family, using first-occurrence instead of frequency counting.

| Goal | Map stores | Update rule |
|---|---|---|
| Count subarrays summing to k | Frequency of each prefix | Add count, then increment |
| Longest subarray summing to k | First occurrence of each prefix | Compare length, store only first |
| Equal zeros and ones | First occurrence of transformed prefix | Same as longest sum = 0 |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• The transformation is the key insight: 0 to -1 converts a counting problem into a zero-sum prefix problem.
• First-occurrence vs frequency: using first-occurrence guarantees maximum length, while frequency counting gives count. Know which to use.
• Offset array optimization: since prefix values range from -N to +N, a new int[2 * N + 1] array with offset N can replace the HashMap for better cache performance.
• Generalization: the same technique works for any balance problem: equal counts of two types, or one type exceeding another by a fixed amount.