# Find Maximum Length Subarray Having an Equal Number of 0’s and 1’s

Posted in

Vinay Khatri
Last updated on June 10, 2022

## Problem

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

#### Sample Input

`[0,1,1,0,1]`

`4`

#### Explanation

The array is [0,1,1,0]

## Brute force approach

The brute force method is quite simple. Within the provided array, we evaluate every conceivable subarray and count the number of zeros and ones in each subarray. Then we find the largest subarray with an equal number of zeros and ones. This approach is inefficient and the time complexity goes upto O(n2).

## Efficient Approach

In this method, we utilize a count variable to track the number of ones and zeros encountered so far while traversing the array. The count variable is increased by one for every 1 encountered and by one for every 0 encountered. We begin our traversal of the array from the beginning. If the count of 0 and 1 ever become equal, it means that we've met an equal number of zeros and ones from the beginning of the array to the current index i Not only that, but if we meet the same count twice when traversing the array, it implies that the number of zeros and ones are the same between them.

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

int findMaxLength(vector<int>&a) {
unordered_map<int,int>mp;
int one=0, zero=0;  //keep track of 1s and 0s
int ans=0;
int n=a.size();
for(int i=0;i<n;i++){
if(a[i]==0) zero++;
if(a[i]==1) one++;
if(zero==one) ans=max(ans,i+1);  // if prefix has equal zero and ones
if(mp.find(zero-one)!=mp.end()){
}
else{
mp[zero-one]=i;
}
}
return ans;
}
int main(){
vectora{1,0,1,0,0};
cout << findMaxLength(a);
}
```

### Python Programming

```def findMaxLengthSubarray(nums):
sum = 0
h = {}
res = 0
for i in range(len(nums)):
if(nums[i] == 0):
sum -= 1
else:
sum += 1
if(sum == 0):
res = max(res, i+1)  #if prefix has equal number of zeros and 1s
elif(sum not in h):
h[sum] = i
else:
res = max(res, i-h[sum]) #update the answer
return res
l = [0,1,0,1,0]
print(findMaxLengthSubarray(l))
```

### C# Programming

```using System;
using System.Collections.Generic;

class Solution
{

static int FindMax(int[] nums) {
var max = 0;
var dif = 0;
var Dif = new Dictionary<int, int> { [0] = -1 };   //create hashmap to store the key-value pair

for (var index = 0; index < nums.Length; index++) {
dif += nums[index] == 1 ? 1 : -1;

if (Dif.TryGetValue(dif, out var start))
max = Math.Max(max, index - start);   // update the answer
else
Dif[dif] = index;
}
return max;
}
public static void Main(String []args)
{
int[] arr = {0, 1, 0, 1, 0};
int n = arr.Length;
Console.WriteLine(FindMax(arr));

}
}```

Output

`4`