Domain 2MediumCORE

Contiguous Array

We are given a binary array containing only 0s and 1s. The goal is to find the maximum length of any contiguous subarray where the count of 0s equals the count of 1s.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table

525. Contiguous Array

Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 43.6%


Problem Breakdown

We are given a binary array containing only 0s and 1s. The goal is to find the maximum length of any contiguous subarray where the count of 0s equals the count of 1s.

Inputs: A list of integers nums (binary values). Outputs: An integer representing the max length found. Constraints: Array size up to 50,000. This rules out O(N^2) solutions like nested loops checking every subarray sum. We need an efficient approach, ideally linear time.

Intuition

A brute-force solution would iterate through all possible start and end indices of a subarray, counting zeros and ones for each slice. That is O(N^3) or at best O(N^2), which will Time Out (TLE).

To optimize this, we need to avoid recounting elements repeatedly. This suggests using prefix sums. If we treat 0 as -1 and 1 as +1, the condition “equal number of 0s and 1s” transforms into a subarray sum equal to zero.

If prefix_sum[i] == prefix_sum[j] (where i < j), it implies that the net change between index i+1 and j is zero. Therefore, the subarray from i+1 to j has an equal number of 0s and 1s.

The key insight: We need a Hash Map to store the first occurrence of each cumulative sum encountered so far. If we encounter that same sum again later, the distance between those two indices is our candidate for the maximum length.

Approach

  1. Initialize max_len at 0 and current_sum at 0.
  2. Create a hash map to store {sum: index}. Crucially, initialize it with {0: -1} before starting the loop. This handles cases where the valid subarray starts from index 0 (since we want distance between current index and virtual start).
  3. Iterate through the array using i as the current index.
  4. Update current_sum: add 1 if element is ‘1’, subtract 1 if it’s ‘0’.
  5. Check if current_sum exists in our map:
    • If yes, calculate length = i - hash_map[current_sum]. Update max_len with the maximum of current and calculated lengths. Do not update the stored index because we want the earliest occurrence to maximize distance.
    • If no, store {current_sum: i} in the map.

Complexity Analysis

  • Time: O(N). We traverse the array exactly once performing constant time hash operations per element. Given N=50k, this is well within limits.
  • Space: O(N). In the worst case (e.g., all 1s), we store every unique cumulative sum in the map before any duplicates appear.

Solution

def findMaxLength(nums):
    # Map to store first occurrence of a prefix sum: {sum -> index}
    # Initialize with sum=0 at index -1 to handle subarrays starting from 0
    hash_map = {0: -1} 
    current_sum = 0
    max_len = 0
    
    for i, num in enumerate(nums):
        # Treat 0 as -1 and 1 as +1. A sum of 0 implies equal counts.
        if num == 1:
            current_sum += 1
        else:
            current_sum -= 1
        
        # If this cumulative sum has been seen before, a valid subarray exists between 
        # the stored index and current index i.
        if current_sum in hash_map:
            max_len = max(max_len, i - hash_map[current_sum])
        else:
            # Store the first occurrence of this sum to maximize future lengths
            hash_map[current_sum] = i
            
    return max_len

Edge Cases Handled

  • Empty Input: The loop simply won’t execute; max_len remains 0, which is correct.
  • All Zeros or All Ones: The cumulative sum will never repeat (it keeps increasing/decreasing). No match found in map after initialization, returns 0 correctly.
  • Subarray starting at index 0: Handled by the {0: -1} initialization. If current_sum becomes 0 immediately, length is calculated as i - (-1).