Contiguous Array

How it works

This approach uses the same logic as the array solution but replaces the fixed-size array with a hash map. The key insight remains the same: if the difference between ones and zeros at two different indices is the same, the subarray between them contains equal zeros and ones. A hash map provides more flexibility and can be more memory-efficient when the array is sparse or when we want cleaner code.

Steps

1. Initialize counters for zeros and ones, and create a hash map to store the first index where each difference value (ones - zeros) occurred.
2. Iterate through the array, incrementing the appropriate counter for each element.
3. If zeros equals ones, the entire prefix is valid, so update the result.
4. Otherwise, check if we've seen the current difference before. If yes, the subarray from that previous index to the current position has equal zeros and ones.
5. Store the difference and its index in the hash map only if it hasn't been stored before (we want the earliest occurrence to maximize length).
6. Return the maximum length found.

Complexity

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

Things to watch for

Forgetting to Initialize the Hash Map with Zero Difference

When the running sum (ones - zeros) becomes zero, the entire prefix from index 0 is valid. To handle this case uniformly, you must initialize the map with {0: -1} or handle it separately. Missing this causes incorrect results for subarrays starting at index 0.

Updating Hash Map Before Checking for Duplicates

You must check if the current difference already exists in the map BEFORE storing the current index. Storing first will overwrite the earlier index, and you want the earliest occurrence to maximize subarray length.

Using Count of Ones Minus Zeros Without the Conversion Trick

The key insight is treating 0s as -1s so that equal counts yield a sum of 0. If you track ones and zeros separately without using this transformation, you cannot efficiently detect when a subarray has equal counts using the hash map approach.

from typing import List

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        zero = one = res = 0
        diff_index = {}

        for i, n in enumerate(nums):
            if n == 0:
                zero += 1
            else:
                one += 1

            if one - zero not in diff_index:
                diff_index[one - zero] = i

            if one == zero:
                res = one + zero
            else:
                idx = diff_index[one - zero]
                res = max(res, i - idx)

        return res

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int zero = 0, one = 0, res = 0;
        unordered_map<int, int> diffIndex;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                zero++;
            } else {
                one++;
            }

            int diff = one - zero;
            if (diffIndex.find(diff) == diffIndex.end()) {
                diffIndex[diff] = i;
            }

            if (one == zero) {
                res = one + zero;
            } else {
                res = max(res, i - diffIndex[diff]);
            }
        }

        return res;
    }
};