Largest Subarray of 0’s and 1’s

Given a binary array A[] consisting of 0’s and 1’s. The task is to return the length of the largest subarray which contains an equal number of 0’s and 1’s.

Examples:

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

Input:  A[] = [1, 0, 1, 1, 1, 0, 0]

Output: 6

Explanation: [0, 1, 1, 1, 0, 0] is the longest subarray with equal number of 0s and 1s.

Approach 1: Brute Force

The most naive approach is to simply generate all possible subarrays of the given array. Now, for each subarray, check whether the count of 0’s and 1’s are the same. If true, maximize the length.

C++ Code

 int findMaxLength(int nums[], int n) {
  int maxlen = 0;
  for (int start = 0; start < n; start++) {
    int zeroes = 0, ones = 0;
    for (int end = start; end < n; end++) {
      if (nums[end] == 0) {
        zeroes++;
      } else {
        ones++;
      }
      if (zeroes == ones) {
        maxlen = max(maxlen, end - start + 1);
      }
    }
  }
  return maxlen;
}

Java Code

public int findMaxLength(int[] nums) {
  int maxlen = 0;
  for (int start = 0; start < nums.length; start++) {
    int zeroes = 0, ones = 0;
    for (int end = start; end < nums.length; end++) {
      if (nums[end] == 0) {
        zeroes++;
      } else {
        ones++;
      }
      if (zeroes == ones) {
        maxlen = Math.max(maxlen, end - start + 1);
      }
    }
  }
  return maxlen;
}

Python Code

def findMaxLength(nums):
    maxlen = 0
    for start in range(0, len(nums)):
        zeroes = 0
        ones = 0
        for end in range(start, len(nums)):
            if nums[end] == 0:
                zeroes += 1
            else:
                ones += 1
 
            if zeroes == ones:
                maxlen = max(maxlen, end - start + 1)
 
    return maxlen

Time Complexity: O(N^2), where N is the size of the array A[] 

Space Complexity: O(1), as no extra space is used.

Approach 2: Using HashMap

The idea is to use a hashmap to store the count of 0’s and 1’s. At any moment, when the count of 0s and 1s are the same, maximize the length of the subarray.

Let us understand this approach with an example:

Algorithm:

• Initialise a hashmap.
• Initialise two variables maxLen = 0 and count = 0.
• Traverse through the array and if the current element A[i] is 1, increment the count, else decrement the value of count.
• Now, check if the value of count is already present in the hashmap:
  • If True, maximize the length of the subarray obtained so far.
• Else, insert (count, i) in the map.
• Return the value of maximum length obtained.
  

Implementation of the Approach:

C++ Code

int findMaxLength(int nums[], int n) {
  map < int, int > map;
  map.insert({0, -1});
  int maxlen = 0, count = 0;
  for (int i = 0; i < n; i++) {
    count = count + (nums[i] == 1 ? 1 : -1);
    if (map.find(count) != map.end()) {
      maxlen = max(maxlen, i - map.get(count));
    } else {
      map.insert({count, i});
    }
  }
  return maxlen;
}

Java Code

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

Python Code

def findMaxLength(self, nums: List[int]) -> int:
 
        count = 0
        
        map = { 0: -1}
        
        max_length = 0
        
        for i, number in enumerate( nums ):
            if number:
                count += 1
            else:
                count -= 1
                
            
            if count in map:
                max_length = max( max_length, ( i - map[count] ) )
                
            else:
                map[ count ] = i
                
        return max_length

Time Complexity: O(N), where N is the size of the array A[] 

Space Complexity: O(N), as a map is used

Practice Questions:

Max Sum Contiguous Subarray

FAQ

• How to find the smallest subarray having equal number of 0s and 1s?
  Following the similar to finding the maximum length having equal zeroes and ones, we need to minimise the length.

• What is the time and space complexity of the hashing approach?
  The time and space complexity of the hashmap approach is O(N).