Find largest subarray with equal numbers of 0’s and 1’s

Learn how to find the largest subarray with equal number of 0’s and 1’s in an given array.

Example

Input:
[0,0,1,0,0,0,1,1]
[0,1,1,0,1,1,1,0]

Output:
6  //100011
4  //0110

In the first example the longest contiguous subarray with equal numbers of 0’s and 1’s is 100011 which is 6.

There are two ways we can solve this problem.

1. Using brute force approach in which we get each subarray and check if they have equal number of 0’s and 1’s and store their count which works in O(n^2) time.
2. Using a hashtable to optimize the problem and solve it O(n) time.

Using brute force approach

We generate each all the subarrays of the array and keep the count of 0’s and 1’s and keep checking if they are equal or not. If they are equal then store the length.

const solution = (arr) => {
  let max = 0;
  for(let i = 0; i < arr.length; i++){
        //To track the count
        let count = {
          0: 0,
          1: 0
        };
        
        for(let j = i; j < arr.length; j++){
          //Increase the count of the respective number
          count[arr[j]]++;
          
          if(count[0] === count[1]){
            max = Math.max(max, count[0] * 2);
          }
        }
    }
  
  return max;
}

Input:
console.log(solution([0,0,1,0,0,0,1,1]));
console.log(solution([0,1,1,0,1,1,1,0]));

Output:
6
4

Time complexity: O(n ^ 2).

Space complexity: O(n).

---

Using hashtable to find the longest contagious subarray with equal number of 0's and 1's.

Implementation

• First convert all the 0's to -1. This it will be really easy to solve the problem.
• Get the cumulative sum of all the elements of the array.
• Case1:- If the sum is 0 then it means there are equal number of 0's and 1's in it.
• Case2:- keep storing the sum and last index in the hash table. In each iteration check if this sum is there or not in the hashtable, if it is there then it means the from sum from last index till the current index is 0 which means there are equal number of 1's and 0's between these indexes, so store its difference.

const solution = (arr) => {
    let hM = new Map();
    let sum = 0;
    let max_len = 0;
    let end_index = -1;    
    let n = arr.length;
    
    //Change all 0's to -1
    for(let i = 0; i < n; i++){
        arr[i] = arr[i] === 0 ? -1 : 1;
    }
    
    for(let i = 0; i < n; i++){
        //Cumulate the sum
        sum += arr[i];
        
        //If sum is 0 then there are equal numbers of -1 and 1 so store the length
        if(sum === 0){
            max_len = i + 1;
            end_index = i;
        }
        
        //Check if the current sum is already present
        //If yes then from last index till current index the sum is 0
        //Which means there are equal no of -1 and 1.
        if(hM.has(sum + n)){
            if (max_len < i - hM.get(sum + n)) { 
                //store the length from last index to current
                max_len = i - hM.get(sum + n); 
                end_index = i; 
            } 
        }else{
            //Store the sum and its index
            hM.set(sum+n, i);
        }
    }
    
    //Return max length
    return max_len; 
};

Input:
console.log(solution([0,0,1,0,0,0,1,1]));
console.log(solution([0,1,1,0,1,1,1,0]));

Output:
6
4

Time complexity: O(n).

Space complexity: O(n).