# Largest Subarray of 0’s and 1’s

Given a binary array A[] consisting of 0’s and 1’s. The task is to return the length of the largest subarray which contains an equal number of 0’s and 1’s.

Examples:

Input: A[] =[0, 1]
Output: 2
Explanation: [0, 1] is the longest subarray with equal number of 0 and 1.

### Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE

Input:  A[] = [1, 0, 1, 1, 1, 0, 0]

Output: 6

Explanation: [0, 1, 1, 1, 0, 0] is the longest subarray with equal number of 0s and 1s.

## Approach 1: Brute Force

The most naive approach is to simply generate all possible subarrays of the given array. Now, for each subarray, check whether the count of 0’s and 1’s are the same. If true, maximize the length.

### C++ Code

``` int findMaxLength(int nums[], int n) {
int maxlen = 0;
for (int start = 0; start < n; start++) {
int zeroes = 0, ones = 0;
for (int end = start; end < n; end++) {
if (nums[end] == 0) {
zeroes++;
} else {
ones++;
}
if (zeroes == ones) {
maxlen = max(maxlen, end - start + 1);
}
}
}
return maxlen;
}```

### Java Code

```public int findMaxLength(int[] nums) {
int maxlen = 0;
for (int start = 0; start < nums.length; start++) {
int zeroes = 0, ones = 0;
for (int end = start; end < nums.length; end++) {
if (nums[end] == 0) {
zeroes++;
} else {
ones++;
}
if (zeroes == ones) {
maxlen = Math.max(maxlen, end - start + 1);
}
}
}
return maxlen;
}```

### Python Code

```def findMaxLength(nums):
maxlen = 0
for start in range(0, len(nums)):
zeroes = 0
ones = 0
for end in range(start, len(nums)):
if nums[end] == 0:
zeroes += 1
else:
ones += 1

if zeroes == ones:
maxlen = max(maxlen, end - start + 1)

return maxlen```

Time Complexity: O(N^2), where N is the size of the array A[]

Space Complexity: O(1), as no extra space is used.

## Approach 2: Using HashMap

The idea is to use a hashmap to store the count of 0’s and 1’s. At any moment, when the count of 0s and 1s are the same, maximize the length of the subarray.

Let us understand this approach with an example:

Algorithm:

• Initialise a hashmap.
• Initialise two variables maxLen = 0 and count = 0.
• Traverse through the array and if the current element A[i] is 1, increment the count, else decrement the value of count.
• Now, check if the value of count is already present in the hashmap:
• If True, maximize the length of the subarray obtained so far.
• Else, insert (count, i) in the map.
• Return the value of maximum length obtained.

Implementation of the Approach:

### C++ Code

```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.get(count));
} else {
map.insert({count, i});
}
}
return maxlen;
}```

### Java Code

```public int findMaxLength(int[] nums) {
Map < Integer, Integer > map = new HashMap < > ();
map.put(0, -1);
int maxlen = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
count = count + (nums[i] == 1 ? 1 : -1);
if (map.containsKey(count)) {
maxlen = Math.max(maxlen, i - map.get(count));
} else {
map.put(count, i);
}
}
return maxlen;
}```

### Python Code

```def findMaxLength(self, nums: List[int]) -> int:

count = 0

map = { 0: -1}

max_length = 0

for i, number in enumerate( nums ):
if number:
count += 1
else:
count -= 1

if count in map:
max_length = max( max_length, ( i - map[count] ) )

else:
map[ count ] = i

return max_length```

Time Complexity: O(N), where N is the size of the array A[]

Space Complexity: O(N), as a map is used

Practice Questions:

Max Sum Contiguous Subarray

## FAQ

• How to find the smallest subarray having equal number of 0s and 1s?
Following the similar to finding the maximum length having equal zeroes and ones, we need to minimise the length.
• What is the time and space complexity of the hashing approach?
The time and space complexity of the hashmap approach is O(N).