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
- Initialize
max_lenat 0 andcurrent_sumat 0. - 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). - Iterate through the array using
ias the current index. - Update
current_sum: add 1 if element is ‘1’, subtract 1 if it’s ‘0’. - Check if
current_sumexists in our map:- If yes, calculate length =
i - hash_map[current_sum]. Updatemax_lenwith 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.
- If yes, calculate length =
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_lenremains 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. Ifcurrent_sumbecomes 0 immediately, length is calculated asi - (-1).