Home » Interview coding problems/challenges

# Length of the largest subarray with equal number of 0s and 1s

**Length of the largest subarray with equal number of 0s and 1s**: Here, we are going to learn how to find the length of the largest subarray with equal number of 0s and 1s? This is a very popular coding problem which has been featured in interview rounds of many big companies such as Amazon, Morgan Stanley, Paytm, MakeMyTrip and others.

Submitted by Divyansh Jaipuriyar, on April 23, 2020

**Problem statement:**

Given an array which consists of * 0's* and

*, your task is to find the maximum lengths of the largest subarray with an equal number of*

**1's***and*

**0's***. The test cases consist of array length and its elements. The first line of the input test cases is the array length*

**1's***and the second line is the array elements.*

**N****Input:**

The first line of the input is * T* denoting the number of test cases. Then

*test cases follow. Each test case contains two lines. The first line of each test case is a number*

**T***denoting the size of the array and in the next line are*

**N***space-separated values of*

**N***.*

**A[]****Output:**

For each test case output in a new line the max length of the subarray.

**Example with explanation:**

Input: T = 1 N = 3 A = [1,0,1] Output: 2 As [1,0] or [0,1] is longest contigous subarray with equal number of 0 and 1. Input: T = 1 N = 6 A = [1 1 0 0 1 0] Output: 6 As [1 1 0 0 1 0],combines to form largest subarray with equal number of zeros and ones.

**Solution Approach**

**1) Brute Force Approach**

We will check every possible subarray within the given array and count the number of zeros and ones in each subarray. If the number of ones and zeros are equal then we store the length of that subarray in our temporary solution, simultaneously we would store the * maxlength* of the subarray by checking the

*with every temporary solution to return it as the final solution.*

**maxlength****Pseudo Code:**

initialise, maxlen=0 for i in range((A)): zerocnt=0,onecnt=0 for j=i in range(A): if(A[j]==0)zerocnt++ if(A[j]==1)onecnt++ if(zerocnt==onecnt) maxlen=(maxlen,j-i+1) Finally return maxlen

The time complexity for the above method in the worst case of **O(n*n)**, where **n**=length of the given Array.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int main() { cout << "Enter number of test cases: "; int t; cin >> t; while (t--) { int n; cout << "Enter size of array: "; cin >> n; int A[n]; cout << "Enter elements: "; for (int i = 0; i < n; i++) cin >> A[i]; int maxlen = 0; for (int i = 0; i < n; i++) { int zerocnt = 0, onecnt = 0; for (int j = i; j < n; j++) { if (A[j] == 0) zerocnt++; if (A[j] == 1) onecnt++; if (zerocnt == onecnt) maxlen = max(maxlen, j - i + 1); } } cout << "Maximum size is: "; cout << maxlen << "\n"; } return 0; }

**Output**

Enter number of test cases: 3 Enter size of array: 4 Enter elements: 1 0 0 1 Maximum size is: 4 Enter size of array: 6 Enter elements: 1 1 0 0 1 0 Maximum size is: 6 Enter size of array: 1 Enter elements: 0 Maximum size is: 0

**2) Hashing Approach**

In this, we will use the hashing technique to beat the time in the best possible manner.

First, we will convert all zeros in the array to **-1** and we would not change the ones since we need to calculate the maxlength of the subarray which have an equal number of ones and zeros(now -1) that is subarray with overall sum equals to zero.

To find the subarray with sum zero we will use a counter which will count the cumulative sum of the array, the hash map key would the cumulative counter value and the hash map value for each key would be the index, if the counter value is already existing in the hash map then it means that it has occurred before, so we take the difference between the current index and the hash map value. We keep storing the temporary length of the subarray having zero-sum and simultaneously checking the * maxlength* of the subarray.

Here we will use

*since it works efficiently in retrieval case.*

**unordered_map****Pseudo Code:**

Initialise, maxlen=0 hashmap<int,int> ma // since index start with 0 and we would avoid to add +1 // each time when we take the difference for length. ma[0]=-1 counter=0 for i in range(A): if(A[i]==0) counter=counter+(-1) else if(A[i]==1) counter=counter+(1) if(ma.find(counter)!=ma.end()) maxlen=max(maxlen,i-ma[counter]) else ma[counter]=i Finally return maxlen

The time complexity for the above case if **O(n)** in the worst case.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int main() { cout << "Enter number of test cases: "; int t; cin >> t; while (t--) { int n; cout << "Enter size of array: "; cin >> n; int A[n]; cout << "Enter elements: "; for (int i = 0; i < n; i++) cin >> A[i]; unordered_map<int, int> ma; ma[0] = -1; int maxlen = 0; int counter = 0; for (int i = 0; i < n; i++) { if (A[i] == 0) counter = counter + (-1); else if (A[i] == 1) counter = counter + (1); if (ma.find(counter) != ma.end()) maxlen = max(maxlen, i - ma[counter]); else { ma[counter] = i; } } cout << "Maximum size is: "; cout << maxlen << "\n"; } return 0; }

**Output**

Enter number of test cases: 3 Enter size of array: 4 Enter elements: 1 0 0 1 Maximum size is: 4 Enter size of array: 6 Enter elements: 1 1 0 0 1 0 Maximum size is: 6 Enter size of array: 1 Enter elements: 0 Maximum size is: 0

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.