Example: Contiguous Array

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Approach

• Transform the problem by treating 0 as -1 and 1 as 1, which allows us to convert the problem into finding the longest subarray with a sum of 0.
• Use a HashMap to track the first occurrence of each prefix sum, this helps us quickly determine if we have seen a particular sum before.
• We start by inserting (0,-1) into the map, meaning we assume an initial prefix sum of 0 before the array begins. This helps in calculating subarrays that start from the beginning.
• We traverse the array maintaining a running sum, either adding or removing 1 based on each array value.
• If we have seen the current sum before, it means that the elements between the previous occurrence and the current sum to 0, the len of this subarray is calculated as i - previousIndex, and we update maxLen accordingly.
• If the sum has not been seen before, we store it in the map for future use.

class Solution {
    public int findMaxLength (int[] nums) {
        // Map to store the first occurrence of each prefix sum
        Map<Integer, Integer> map= new HashMap<>();
       
        int maxLength = 0;
        int sum = 0;
        
        // Traverse the array
        for (int i = 0; i < nums.length; i++) {
            // Treat 0 as -1 and 1 as 1
            sum += (nums[i] == 1) ? 1 : -1;
            if (sum == 0) {
                max = i + 1;
                continue;
            }
            // If this prefix sum has been seen before, a subarray with sum 0 is found
            if (map.containsKey (sum)) {
                // Calculate the length of the subarray
                maxLength = Math.max (maxLength, i - map.get (sum));
            } else {
                // If this is the first time seeing this prefix sum, record the index
                map.put (sum, i);
            }
        }
        
        return maxLength;
    }
}