Get this book -> Problems on Array: For Interviews and Competitive Programming

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.