×

Search anything:

# Largest sub-array with equal number of 1 and 0

#### Algorithms prefix sum array hash map

Indian Technical Authorship Contest starts on 1st July 2023. Stay tuned.

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.

#### Bhavani Sankar Nagarapu

Bhavani is pursuing bachelorâ€™s degree in Electrical Engineering from GIET College of Engineering and am a SDE Intern at OpenGenus.