Contiguous Array

---

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

Example 1:

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

---

Example 2:

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.

---

Try this Problem on your own or check similar problems:

1. Maximum Size Subarray Sum Equals k

Solution:

Java

public int findMaxLength(int[] nums) {
  Map<Integer, Integer> map = new HashMap<>();
  map.put(0, -1);
  int maxLength = 0, sum = 0;

  for(int i = 0; i < nums.length; ++i){
      sum += nums[i] == 0 ? -1 : 1;
      if(map.containsKey(sum)){
        maxLength = Math.max(maxLength, i - map.get(sum));
      }else{
        map.put(sum, i);
      }
  }

  return maxLength;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function (nums) {
  const map = new Map();
  map.set(0, -1);
  let maxLength = 0;
  let sum = 0;

  for (let i = 0; i < nums.length; ++i) {
    sum += nums[i] === 0 ? -1 : 1;
    if (map.has(sum)) {
      maxLength = Math.max(maxLength, i - map.get(sum));
    } else {
      map.set(sum, i);
    }
  }

  return maxLength;
};

Python

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        map = {}
        map[0] = -1
        maxLength = 0
        sum = 0

        for i in range(len(nums)):
            sum += -1 if nums[i] == 0 else 1
            if sum in map:
                maxLength = max(maxLength, i - map[sum])
            else:
                map[sum] = i

        return maxLength

C++

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> map;
        map[0] = -1;
        int maxLength = 0;
        int sum = 0;

        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i] == 0 ? -1 : 1;
            if (map.find(sum) != map.end()) {
                maxLength = max(maxLength, i - map[sum]);
            } else {
                map[sum] = i;
            }
        }

        return maxLength;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

We traverse the input array once and we also keep a map (prefix sum) leading to linear space and time complexity. This problem can be transformed into prefixSum just like we had in Range Query Sum Immutable. But there are several tricks we have to do to make it work:

• 0 is neutral to addition, but we know that we only have 1 or 0 in the input array, so each time we encounter 0 we can transform it to 1 counterpart -1
• The reason we immediately fill the map with (0, -1) pair is if we have subarray 0,1 the sum is 0 (-1 for the first 0, and then 1 for the 1), so to make it easy on us we find the length using phantom index -1 leading to length i=1, length = 1 - (-1) = 2
• How do we know there is equal number of 0 and 1 between two indices of array, well if we have the same sum as before for index j on a matching sum index i, we know that elements between them produced 0 in total since the sums are equal. Let's say for example we have array 0, 1, 0, 1, 0 at index i = 2 the sum will be -1 so we store it in map (-1, 2), next time we hit 0 at index 4 the sum is again -1, so we know that elements between index 2 and index 4 sum up to 0 (equal number of ones and zeroes).