**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 subarrayExample 2:Input:arr[] = {0, 0, 1, 1, 0}Output:0 to 3 Or 1 to 4Example 3:Input:arr[] = {1, 0, 1, 1, 1, 0, 0}Output:1 to 6Starting index and ending index is given ofthe longest subarray with equal 1's and 0's

**Solution**

** Disclaimer**:

*Don’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) {
// write your code here
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.

Special thanks toplease check out this articleAmisha Kumarifor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,