# Longest Subarray with an equal 0s and 1s

Problem statement: Given an array containing only 0s and 1s, find the largest subarray which contains an equal no of 0s and 1s.

Examples:

```Example 1:
Input: arr[] = {1, 1, 1, 1}

Output: No such subarray

Example 2:
Input: arr[] = {0, 0, 1, 1, 0}

Output: 0 to 3 Or 1 to 4

Example 3:
Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6

Starting index and ending index is given of
the longest subarray with equal 1's and 0's```

### Solution

DisclaimerDon’t jump directly to the solution, try it out yourself first.

### Solution 1: Brute Force.

Approach:

• Use two nested loops.
• Take variable sum = 0, at its start, in which we will take our cumulative sum from all the sub-arrays.
• The outer loop picks a starting point i = 0 and the inner loop will start from j = i + 1.
• Start taking the sum from all the subarrays, whenever we get sum value = 0, it means it has an equal number of 1s and 0s.
• Now compare every size with the longest subarray(maxlen variable), if we got the max size than the longest subarray we will update our subarray in the maxlen variable.
• Return the longest subarray maxlen startIndex and Size

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

int findSubArray(int nums[], int n) {
int sum = 0;
int maxlen = -1, startindex;

// Pick a starting point as i
for (int i = 0; i < n - 1; i++) {
sum = (nums[i] == 0) ? -1 : 1;

// Consider all subarrays starting from i
for (int j = i + 1; j < n; j++) {
(nums[j] == 0) ? (sum += -1) : (sum += 1);

// If this is a 0 sum subarray, then
// compare it with maximum size subarray
if (sum == 0 && maxlen < j - i + 1) {
maxlen = j - i + 1;
startindex = i;
}
}
}
if (maxlen == -1)
cout << "No such subarray";
else
cout << "The length of the longest subarray is: " << maxlen;
}

/* Driver code*/
int main() {
int arr[] = { 1, 0, 0, 1, 0, 0, 1 };
int size = sizeof(arr) / sizeof(arr[0]);

findSubArray(arr, size);
return 0;
}``````

Output: The length of the longest subarray is: 4

Time Complexity: O(N^2) as We consider every possible subarray by traversing over the complete array for every start point possible.

Space Complexity: O(1) as Only two variables zeros and ones are required

## Java Code

``````class LongestSubArray {

void findSubArray(int nums[], int n) {
int sum = 0;
int maxlen = -1, startindex = 0;
int endindex = 0;

// Pick a starting point as i

for (int i = 0; i < n - 1; i++) {
sum = (nums[i] == 0) ? -1 : 1;

// Consider all subarrays starting from i

for (int j = i + 1; j < n; j++) {
if (nums[j] == 0)
sum += -1;
else
sum += 1;

// If this is a 0 sum subarray, then
// compare it with maximum size subarray

if (sum == 0 && maxlen < j - i + 1) {
maxlen = j - i + 1;
startindex = i;
}
}
}

if (maxlen == -1)
System.out.println("No such subarray");
else
System.out.println("The length of the longest subarray is: " + maxlen);
}

/* Driver program to test the above functions */

public static void main(String[] args) {
LongestSubArray sub;
sub = new LongestSubArray();
int arr[] = { 1, 0, 0, 1, 0, 0, 1  };
int size = arr.length;
sub.findSubArray(arr, size);
}
}``````

Output: start index 0 to end index 3

Time Complexity: O(N^2) as We consider every possible subarray by traversing over the complete array for every start point possible.

Space Complexity: O(1) as Only two variables zeros and ones are required

### Solution 2: Optimal Solution(Hashmap)

Approach:

• Convert all the “0” to “-1” in the example, so that we get something like :-

[0, 0,1,0,1,0]. If you see this, the problem is somewhat like returning the longest subarray length whose sum is “ZERO”.

• As the question is telling us to return same/equal numbers of zeros and ones.
• So, that means the same as well there will be equal no. of 1 & -1 .
•  sum  1 + (-1) = 0,we conclude that we need to return that subarray length, whose sum is 0 with the longest subarray.

In our hashMap, we will have key & value.

• At start max = 0 and so index will be -1 and cumulative sum = 0.
• We move further to get a max of 1. And in our hashmap for reference we put the key 0 -> -1 value.
• We will check in our key value pair if we have the pair of 1? As at index 0 ->0
• No there is no pair of 1 we will move forward by adding sum = -1 and -1(at 1st index) = sum = -1+ -1 = -2
• Move forward and check the index(2) we got 1 that means sum = -2 + 1 = -1.
• Since we already have -1 in our map, that means there is a subarray and length = 2 (index(2) – index(0))  ,subarray = [0,1]
• Now moving further & at index 3 we got a gain of 1 as Our cumulative sum is  = -1 + -1 = -2 And if we look at hashmap -2 is already present there is a subarray, length index(3-2) = 1 will not update the length here 1 < 2,
• At index 4 we have 1 so sum = -2 + 1 = -1 and  -1 is already in the hashmap at index 1 and 0 length from 0 to 4 = index(4 – 0) = 4 another one is index(4 – 3) = 1 max-length = 4
• Finally, our max-length = 4.

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

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[count]);
} else {
map.insert({count,i});
}
}
cout << "The length of the longest subarray is: " << maxlen;
}

/* Driver code*/
int main() {
int arr[] = { 1, 0, 0, 1, 0, 0, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
findMaxLength(arr, size);
return 0;
}``````

Output: The length of the longest subarray is: 4

Time Complexity: O(N) where n is the size of an array.

Space Complexity: O(n) as map used.

## Java Code

``````import java.util.*;
class LongestSubArray {

public static void findMaxLength(int[] arr) {

int max = 0;

HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, -1); // at the starting we will put -1 for 0

int sum = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
sum += -1; //whenever we have 0 = -1
} else if (arr[i] == 1) {
sum += +1; // whenever we have 1 = 1
}
if (map.containsKey(sum)) {
int idx = map.get(sum);
int length = i - idx;
if (length > max) {
max = length;
}
} else {
map.put(sum, i);
}

}
System.out.println("The length of the longest subarray is: " + max);

}

public static void main(String[] args) {
int arr[] = { 1, 0, 0, 1, 0, 0, 1  };
int size = arr.length;
findMaxLength(arr);
}
}``````

Output: The length of the longest subarray is: 4

Time Complexity: O(N) where n is the size of an array.

Space Complexity: O(n) as map used.