AlgoMaster Logo

Contiguous Array

Last Updated: March 21, 2026

medium
3 min read

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. So for a subarray of length 6 to qualify, it needs exactly 3 zeros and 3 ones. The subarray must be contiguous, meaning the elements have to be consecutive in the original array.

The brute force instinct is to check every possible subarray and count 0s and 1s. But with arrays up to 100,000 elements long, we need something smarter.

Here's the key insight: if we treat every 0 as -1, then a subarray with equal 0s and 1s has a sum of exactly 0. Why? Because each 0 contributes -1 and each 1 contributes +1. Equal counts means they cancel out perfectly. This transforms our problem into finding the longest subarray with sum 0, which is a well-known prefix sum problem.

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] is 0 or 1 → Binary values simplify counting. The 0-to-(-1) transformation is clean since there are only two possible values.

Approach 1: Brute Force

Intuition

The most straightforward idea: try every possible subarray and check if it has 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 what anyone would try first. It's correct and easy to reason about, just slow.

Algorithm

  1. Initialize maxLen to 0
  2. For each starting index i from 0 to n-1:
  3. Initialize counters for zeros and ones to 0
  4. For each ending index j from i to n-1:
  5. Increment the appropriate counter based on nums[j]
  6. If zeros equals ones, update maxLen with j - i + 1
  7. Return maxLen

Example Walkthrough

1Initialize: maxLen=0, try every subarray
0
j
0
i
1
1
2
0
1/8

Code

For every starting index, we scan forward counting 0s and 1s from scratch, even though adjacent subarrays share most of their counts. What if we could compute a running total once and use it to instantly determine the count balance for any subarray?

Approach 2: Prefix Sum + Hash Map

Intuition

Here's the transformation that makes everything click: replace every 0 in the array with -1. Now every 0 subtracts 1 from the running sum, and every 1 adds 1. A subarray with equal 0s and 1s has an equal number of +1s and -1s, so its sum is exactly 0.

Finding the longest subarray with sum 0 is a classic prefix sum problem. 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 index i, that means the subarray from i+1 to j has a sum of 0. Why? Because everything added between those two indices cancelled out.

So the algorithm becomes: compute the running prefix sum, and use a hash map to record the first time each sum value appears. When you see a sum you've already recorded, the distance from that first occurrence to the current index is a candidate for the longest subarray.

One subtle detail: we initialize the map with sum 0 at index -1. This handles the case where the subarray starting from the very beginning has sum 0. Without this initialization, we'd miss subarrays like [0, 1] where the prefix sum returns to 0.

Algorithm

  1. Create a hash map and insert (0, -1) to handle subarrays starting from index 0
  2. Initialize prefixSum to 0 and maxLen to 0
  3. For each index i in the array:
  4. Add +1 if nums[i] is 1, or -1 if nums[i] is 0, to prefixSum
  5. If prefixSum exists in the map, update maxLen with i - map[prefixSum]
  6. Otherwise, store prefixSum with index i in the map
  7. Return maxLen

Example Walkthrough

1Initialize: prefixSum=0, map={0:-1}, maxLen=0
0
0
i
1
1
2
0
1/6

Code