Longest Subarray with Equal 0s and 1s Using Hash Map

function findMaxLength(nums) {
  const map = new Map();
  map.set(0, -1);
  let sum = 0, maxLen = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i] === 0 ? -1 : 1;
    if (map.has(sum)) {
      maxLen = Math.max(maxLen, i - map.get(sum));
    } else {
      map.set(sum, i);
    }
  }
  return maxLen;
}
                  

Explanation: Convert 0s to -1. Then use prefix sum and hash map. Repeated sums indicate equal number of 0s and 1s in between.

⏱ O(n) | 💾 O(n)

class Solution {
  public int findMaxLength(int[] nums) {
    Map<Integer,Integer> map = new HashMap<>();
    map.put(0,-1);
    int sum=0,maxLen=0;
    for(int i=0;i<nums.length;i++){
      sum += nums[i]==0?-1:1;
      if(map.containsKey(sum)) maxLen = Math.max(maxLen,i-map.get(sum));
      else map.put(sum,i);
    }
    return maxLen;
  }
}
                  

Explanation: Prefix sum method with 0 as -1. HashMap stores earliest index for each sum. Difference gives max length subarray with equal 0s and 1s.

⏱ O(n) | 💾 O(n)

def find_max_length(nums):
    d = {0:-1}
    total = 0
    maxlen = 0
    for i,num in enumerate(nums):
        total += -1 if num==0 else 1
        if total in d:
            maxlen = max(maxlen,i-d[total])
        else:
            d[total] = i
    return maxlen
                  

Explanation: Treat 0 as -1 and compute prefix sums. Repeated sums indicate subarray with equal 0s and 1s.

⏱ O(n) | 💾 O(n)