Problem Description

The Contiguous Array problem on LeetCode asks you to find the length of the longest contiguous subarray within a binary array (an array containing only 0s and 1s) that contains an equal number of 0s and 1s.

• You are given an array called nums consisting of only 0s and 1s.
• Your task is to return the maximum length of a contiguous subarray with an equal number of 0s and 1s.
• Each element can only be used once and subarrays must be contiguous (no skipping elements).
• There may be multiple valid subarrays, but you only need to return the length of the longest one.

Example:
Input: nums = [0,1,0]
Output: 2
Explanation: The contiguous subarray [0,1] or [1,0] has equal numbers of 0s and 1s.

Thought Process

At first glance, you might think about checking every possible subarray and counting the number of 0s and 1s in each. However, this would be very inefficient for large arrays, as there are many possible subarrays.

Instead, we look for a way to quickly determine if a subarray has equal numbers of 0s and 1s. One key insight is that if we treat 0 as -1 and 1 as +1, then the problem reduces to finding the longest subarray whose sum is zero.

This is similar to the classic "subarray sum equals k" problem, and suggests we can use a hash map to store the first occurrence of each cumulative sum. This allows us to efficiently find the longest subarray where the number of 0s and 1s are equal.

Solution Approach

• Step 1: Replace every 0 in the array with -1.
  • This way, when you sum up a subarray, a sum of 0 means equal numbers of 0s and 1s.
• Step 2: Use a variable count to keep track of the running sum as you iterate through the array.
• Step 3: Use a hash map (count_to_index) to store the earliest index at which each count value has occurred.
  • If the same count value appears again at a later index, it means the subarray between those indices has a net sum of 0 (i.e., equal numbers of 0s and 1s).
• Step 4: As you iterate, for each index:
  • If the current count has been seen before, calculate the length of the subarray from the previous index to the current index and update the maximum length.
  • If not, record the current index for this count in the hash map.
• Step 5: Return the maximum length found.

We use a hash map because it allows us to look up whether we've seen a particular count value before in constant time, which is crucial for efficiency.

Example Walkthrough

Let's consider the input nums = [0, 1, 0, 1, 1, 0, 0].

1. Replace 0 with -1: [-1, 1, -1, 1, 1, -1, -1]
2. Initialize count = 0 and count_to_index = {0: -1} (to handle the case where the subarray starts at index 0).
3. Iterate through the array, updating count and checking if it has been seen before:
   • Index 0: count = -1. Not seen before. Store -1: 0.
   • Index 1: count = 0. Seen at index -1. Length = 1 - (-1) = 2. Update max_length = 2.
   • Index 2: count = -1. Seen at index 0. Length = 2 - 0 = 2. Max_length remains 2.
   • Index 3: count = 0. Seen at index -1. Length = 3 - (-1) = 4. Update max_length = 4.
   • Index 4: count = 1. Not seen before. Store 1: 4.
   • Index 5: count = 0. Seen at index -1. Length = 5 - (-1) = 6. Update max_length = 6.
   • Index 6: count = -1. Seen at index 0. Length = 6 - 0 = 6. Max_length remains 6.
4. The longest contiguous subarray has length 6.

Time and Space Complexity

• Brute-force approach:
  • Check every possible subarray and count 0s and 1s.
  • Time complexity: O(n^2) because there are O(n^2) subarrays.
  • Space complexity: O(1) (ignoring input and output).
• Optimized hash map approach:
  • Time complexity: O(n) because we iterate through the array once and hash map operations are constant time.
  • Space complexity: O(n) for the hash map (in the worst case, all prefix sums are unique).

Summary

The key to solving the Contiguous Array problem efficiently is to recognize that by mapping 0s to -1s, the problem reduces to finding the longest subarray with sum zero. Using a hash map to store the first occurrence of each running sum allows us to check in constant time whether a subarray with equal numbers of 0s and 1s exists up to any index. This approach turns a brute-force O(n^2) problem into a clean and efficient O(n) solution.

Code Implementation

class Solution:
    def findMaxLength(self, nums):
        count_to_index = {0: -1}
        count = 0
        max_length = 0
        for i, num in enumerate(nums):
            count += 1 if num == 1 else -1
            if count in count_to_index:
                max_length = max(max_length, i - count_to_index[count])
            else:
                count_to_index[count] = i
        return max_length
      

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> count_to_index;
        count_to_index[0] = -1;
        int count = 0, max_length = 0;
        for (int i = 0; i < nums.size(); ++i) {
            count += (nums[i] == 1) ? 1 : -1;
            if (count_to_index.find(count) != count_to_index.end()) {
                max_length = max(max_length, i - count_to_index[count]);
            } else {
                count_to_index[count] = i;
            }
        }
        return max_length;
    }
};
      

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> countToIndex = new HashMap<>();
        countToIndex.put(0, -1);
        int count = 0, maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            count += (nums[i] == 1) ? 1 : -1;
            if (countToIndex.containsKey(count)) {
                maxLength = Math.max(maxLength, i - countToIndex.get(count));
            } else {
                countToIndex.put(count, i);
            }
        }
        return maxLength;
    }
}
      

var findMaxLength = function(nums) {
    const countToIndex = new Map();
    countToIndex.set(0, -1);
    let count = 0, maxLength = 0;
    for (let i = 0; i < nums.length; i++) {
        count += nums[i] === 1 ? 1 : -1;
        if (countToIndex.has(count)) {
            maxLength = Math.max(maxLength, i - countToIndex.get(count));
        } else {
            countToIndex.set(count, i);
        }
    }
    return maxLength;
};