Contiguous Array
Understanding the Problem
We have an array of only 0s and 1s, and we need to find the longest contiguous subarray where the count of 0s equals the count of 1s. A subarray of length 6 qualifies only if it contains exactly 3 zeros and 3 ones. The subarray must be contiguous, meaning the elements have to be consecutive in the original array.
Checking every possible subarray and counting its 0s and 1s works, but with arrays up to 100,000 elements long, that quadratic scan is too slow.
The problem has a useful reformulation. Treat every 0 as -1, so each 0 contributes -1 and each 1 contributes +1 to a running sum. A subarray with equal counts then sums to exactly 0, and the task becomes finding the longest subarray with sum 0, which prefix sums solve in linear time.
Key Constraints:
nums.length <= 10^5→ We need O(n) or O(n log n). An O(n^2) brute force with 10^10 operations is too slow.nums[i]is0or1→ Binary values simplify counting. The 0-to-(-1) transformation is clean since there are only two possible values.
Approach 1: Brute Force
Intuition
Check every possible subarray for equal 0s and 1s. For each starting index, extend the subarray one element at a time, keeping a running count of 0s and 1s. Whenever the counts match, update the maximum length. This is correct and easy to reason about, but slow.
Algorithm
- Initialize
maxLento 0 - For each starting index
ifrom 0 to n-1: - Initialize counters for zeros and ones to 0
- For each ending index
jfromito n-1: - Increment the appropriate counter based on
nums[j] - If zeros equals ones, update
maxLenwithj - i + 1 - Return
maxLen
Example Walkthrough
Code
- Time Complexity: O(n^2). Two nested loops, each running up to n iterations. For each starting index, we potentially scan the rest of the array.
- Space Complexity: O(1). Only a few integer variables are used, no extra data structures.
For every starting index, the inner loop recounts elements that earlier subarrays already covered. The next approach computes one running total over the whole array and reads the balance of any subarray from it in constant time.
Approach 2: Prefix Sum + Hash Map
Intuition
With every 0 treated as -1, the goal is the longest subarray with sum 0, and prefix sums answer that directly. The prefix sum at index i is the sum of all elements from index 0 to i. If the prefix sum at index j equals the prefix sum at an earlier index i, every +1 and -1 added between i+1 and j cancelled out, so the subarray from i+1 to j sums to 0.
The algorithm follows from that fact: compute the running prefix sum, and use a hash map to record the first index at which each sum value appears. When the current sum has been recorded before, the distance from that first occurrence to the current index is a candidate for the longest subarray.
The map is initialized with sum 0 at index -1 to cover subarrays that start at index 0. Without this entry, a balanced prefix like [0, 1] would go undetected, because the sum 0 it returns to was never stored.
Storing only the first occurrence of each prefix sum guarantees the longest possible subarray for that value. If a sum appears at indices 2, 5, and 9, pairing index 2 with index 9 gives length 7, while pairing index 5 with index 9 gives only 4. The code preserves this by never overwriting an existing entry: a sum already in the map keeps its leftmost index.
Algorithm
- Create a hash map and insert (0, -1) to handle subarrays starting from index 0
- Initialize
prefixSumto 0 andmaxLento 0 - For each index
iin the array: - Add +1 if
nums[i]is 1, or -1 ifnums[i]is 0, toprefixSum - If
prefixSumexists in the map, updatemaxLenwithi - map[prefixSum] - Otherwise, store
prefixSumwith indexiin the map - Return
maxLen
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the array once. Each hash map lookup and insertion is O(1) on average. Total work is linear.
- Space Complexity: O(n). In the worst case, every prefix sum is unique (e.g., all 1s: sums go 1, 2, 3, ..., n), so the hash map stores n entries.