Problem

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of0 and1.

Examples

Example 1:

1
2
3

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

1
2
3

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Constraints:

  • 1 <= nums.length <= 10^5
  • nums[i] is either 0 or 1.

Solution

Method 1 - Using Prefix Sum

To solve this problem, we use a hash map to store a prefix sum and its corresponding index. The key idea is to transform the problem into finding subarrays where the sum of elements is zero after mapping 0 to -1. For each element in the array, calculate the running difference (prefix sum) between the number of 1s and 0s. If this difference has been seen before, the subarray between the previous index and the current index has an equal number of 0s and 1s.

Approach

  1. Transform the Array: Map 0 to -1 while traversing. This makes finding an equal number of 0 s and 1 s equivalent to finding a subarray with a sum of 0.
  2. Use Hash Map: Store prefix_sum as keys and their first occurrence index as values. If the same prefix_sum appears again later, the subarray between these indices has a sum of zero, indicating an equal number of 0 s and 1 s.
  3. Iterate Over nums: Use the hash map to check if the current prefix sum was seen earlier. Calculate the length of the subarray (current index - previous index) and update the maximum length (ans).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {

    public int findMaxLength(int[] nums) {
        int ans = 0, prefixSum = 0;
        HashMap<Integer, Integer> indexMap = new HashMap<>();
        indexMap.put(0, -1); // Initialize prefix_sum 0 at index -1

        for (int i = 0; i < nums.length; i++) {
            // Map 0 to -1 for prefix sum calculation
            prefixSum += nums[i] == 0 ? -1 : 1;

            if (indexMap.containsKey(prefixSum)) {
                ans = Math.max(ans, i - indexMap.get(prefixSum));
            } else {
                indexMap.put(prefixSum, i);
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        ans = 0
        prefix_sum = 0
        index_map: dict[int, int] = {0: -1}  # Initialize with prefix_sum 0 at index -1

        for i, num in enumerate(nums):
            # Map 0 to -1 for prefix sum calculation
            prefix_sum += -1 if num == 0 else 1
            
            if prefix_sum in index_map:
                ans = max(ans, i - index_map[prefix_sum])
            else:
                index_map[prefix_sum] = i

        return ans

Complexity

  • ⏰ Time complexity: O(n) as we traverse the array once and perform constant-time operations for each element (hash map lookup and update).
  • 🧺 Space complexity: O(n) as we store prefix sums in a hash map, which in the worst case could grow to the size of the input array.