In this article, we have explored 3 different approaches to find the Largest sub-array with equal number of 1 and 0. This involve the concept of Hash Map/ Set and Prefix Sum.

Problem Statement

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

Example

Input: arr = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with an equal number of 0 and 1
Constraints:
1 <= nums.length <= 105
nums[i] is either 0 or 1.

Solution Approach

Approach 1: BruteForce

Alogorithm

• In this approach, we will check every subarray whether it contains equal number of 0's & 1's.
• Firstly, we will initialize some variables that are needed. They are as follows:
  • zeroes : It is used to count 0's in subarray and it is integer type.
  • ones : It is used to count 1's in subarray and it is integer type.
  • maxlen : It is used to track the maximum possible length of a subarray which contains equal number of 0's & 1's.
• To check each subarray we need two loops whose signifies start and end of subarray.

Implementation

• bruteforce implementation in java:

import java.util.Scanner;
public class Solution {
    static Scanner s = new Scanner(System.in);
    public int findMaxLength(int[] arr) {
        // variable to track maximum length
        int maxlen = 0;
        // array length
        int n = arr.length;    
        for (int s = 0; s < n; start++) {
            // Initialize zeroes & ones to 0
            int zeroes = 0, ones = 0;       
            for (int e = s; e < n; end++) {
                //if element is 0 increase zeroes by 1
                if (nums[end] == 0) {
                    zeroes++;
                }
                //if element is 1 increase ones by 1
                else {
                    ones++;
                }
                //checking subarray whether it contains equal number of 0's & 1's
                if (zeroes == ones) {
                    maxlen = Math.max(maxlen, e - s + 1);
                }
            }
        }
        return maxlen;
    }
    public static void main (String args[]) {
        int n = sc.nextInt();    // take input for arr size
        int arr[] = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = nextInt();     // take input for array values
        }
        System.out.println(findMaxLength(arr));
}

Complexity Analysis

• Time Complexity: O(n^2). As we checking every possible sub array.
• Space Complexity: O(1) . we only used three integer variables zeroes, ones and maxlen.

Approach 2: Using Hashmap

Algorithm

• In this approach, we will use hashmap to keep track of count of 0's & 1's corresponding to index of array while we traversing through out the array.
• we make use of a HashMap map to store the entries in the form of (index,count).
• we will use the correspoding index to find the length of the largest subarray with equal no. of zeros and ones when the same count is encountered again.
• we will the use following variables:
  • maxlen: It is used to track the maximum possible length of a subarray which contains equal number of 0's & 1's.
  • count: It counts no. of 1's with increase by 1 and 0's with decrease by 1.

Implementation

• implemenation using hashmap in Java:

import java.util.Scanner;
public class Solution {
    static Scanner s = new Scanner(System.in);
    public int findMaxLength(int[] arr) {
        // create hashmap for <int, int> 
        Map<Integer, Integer> map = new HashMap<>();
        // initially count = 0, index = -1
        // hashmap is in form (count, index)
        map.put(0, -1);
        int maxlen = 0, count = 0;
        for (int i = 0; i < arr.length; i++) {
            // add 1 or -1 to count whether arr[i] is equal to 1 
            count = count + (arr[i] == 1 ? 1 : -1);
            if (map.containsKey(count)) {
                maxlen = Math.max(maxlen, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return maxlen;
    }
    public static void main (String args[]) {
        int n = sc.nextInt();    // take input for arr size
        int arr[] = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = nextInt();     // take input for array values
        }
        System.out.println(findMaxLength(arr));
    }
}

Complexity Analysis

• Time Complexity: O(n). as we iterating through the array once.
• Space Complexity: O(n). If all the elements are either 1 or 0, the maximum possible size of hashmap will be n.

Approach 3: Using PrefixSum

Algorithm

• In this approach, we use prefixsum to calculate the length of the longest subarray which contains equal no. of 0's & 1's
• PrefixSum is also known as CumulativeSum. The cumulative sums are the total sums up to the respective position.
• And also, we replace 0 with -1 for our convenience. This approach is slightly similar to the 2nd Approach.
• The sum of longest subarray elements should be 0.
• We have to return that subarray length, whose sum is 0.

Implementation

import java.util.*;

public class Solution {
    static Scanner s = new Scanner(System.in);
    public int findMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) { // Base Case
            return 0;
        }
        // Converting all 0 to -1
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0) nums[i] = -1;
        }
        int sum = 0; // current
        int max = 0; // final-ans
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // put reference in the starting of 0 & -1, as i have tell you in the starting  
        for(int i = 0; i < nums.length; i++){
            sum += nums[i]; // cumulative sum
            if(map.containsKey(sum)){ // if cumulative sum key :- 0, -1, 1 already present
                int last = map.get(sum); // we get it's value
                max = Math.max(max, i - last); // and update max
            }
            else{ // if it's not present then create it's key-value pair
                map.put(sum, i);
            }
        }
        return max; // finally return it
    }
    
    public static void main(String args[]) {
        int n = s.nextInt();        // take input for length of array
        int arr[] = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = nextInt();     // take input for array values
        }
        System.out.println(findMaxLength(arr));
    }
}

Complexity Analysis

• Time Complexity: O(n). as we iterating through the array once.
• Space Complexity: O(n). The maximum possible size of hashmap will be n.

With this article at OpenGenus, you must have the complete idea of solving this problem of finding largest sub-array with equal number of 1 and 0.