# Largest subarray with equal number of 0s and 1s

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

Examples:

Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1}
Output: 1 to 8 (Starting and Ending indexes of output sub array)

Implementation:
In this method,use two nested loops. The outer loop picks a starting point i. The inner loop considers all subarrays starting from i. If size of a subarray is greater than maximum size so far, then update the maximum size.
In this implementation, 0s are considered as -1 and sum of all values from i to j is calculated. If sum becomes 0, then size of this subarray is compared with largest size so far. Complexity of this method is O(n^2).

```int findLargestSubArray(int arr[], int n)
{
int sum = 0;
int maxsize = -1, fromIndex;

// Pick a starting point as i
for (int i = 0; i < n-1; i++)
{
if(arr[j] == 0)
sum = -1;
else
sum = 1;

// Consider all subarrays
for (int j = i+1; j < n; j++)
{
if(arr[j] == 0)
sum += -1;
else
sum += 1;

/* If this is a 0 sum subarray, then compare it with
maximum size subarray calculated so far */
if(sum == 0 && maxsize < j-i+1)
{
maxsize = j - i + 1;
fromIndex = i;
}
}
}

return maxsize;
}
```

Time Complexity: O(n^2)
Auxiliary Space: O(1)

### 0 Thoughts on “Largest subarray with equal number of 0s and 1s”

1. sid_Python on January 31, 2014 at 4:59 pm said:

O(nlgn) time) and O(n) space

int findLargestSubArray(int arr[], int n)
{
int i = 0,max = 0,index = 0;
stack s = NULL;
if (0 >=n)
return -1;
push(&s,arr[0])
for (i =1; i max)
max = index;
}
if (s.empty())
return n;
else
return max;
}

2. Hari Ram Choudhary on February 26, 2014 at 8:31 am said:

Neha Garg I don't know which algorithm can improve time complexity but what approach is given here is just a brute force approach.

3. can be done in O(n) time and space … asked in Gate2006 CS exam.

4. [email protected] on July 12, 2014 at 1:20 am said:

Time Complexity : O(n)
Auxiliary Space : O(n)

public static int maxLength(String line){
int counter = 0;
int max = 0;
int[] minPos = new int[line.length()*2+1];
for(int i = 0;i<line.length();i++){
boolean isOne = line.charAt(i) == '1';
counter = isOne ? counter+1 : counter-1;
if(counter==0){
max = i+1;
}else{
int lastPosOcurr = minPos[counter+line.length()];
if(lastPosOcurr!=0){
max = Math.max(max, i-lastPosOcurr);
}
}
}
return max;
}

5. Can be done in O(n)
take a global max=0;
treat 0 as -1
a) make cummulative sum and keep hashing them
b) once you find that hash value again update the size of max as (current_index-hash[arr[current_index]])

see code in c++

let int arr[]={};
map hash;
hash.clear();
for(int i=0;i<n;i++)
{
int temp;
if(arr[i]==0)
temp=-1;

6. #Largest subarray with equal number of -1s and 1s
def max_sub_array(a):
st=0;
sum=a[0]
end=0
i=1;
n=len(a)
while(i<n):
sum += a[i]
if(sum == 0):
end=i;
i = i + 1

if(i==n and sum != 0) :
end = n
if(sum < 0):
st = st – sum
else:
st = st + sum
print "Input array "+str(a)
print "largest sub array with equal number of -1 and 1 start with =" + str(st) +"end with =" + str(end)
print "largest sub array"+str(a[st:end+1])

a=[-1,1,1,1,-1,-1,1,-1,1,1,1]
max_sub_array(a)
b=[-1,-1,-1,1,1]
max_sub_array(b)
c=[1,1,1,-1]
max_sub_array(c)

7. Anonymous on August 26, 2014 at 7:27 am said:

#include <iostream>

using namespace std;

int main()
{
int arr[] = {1, 0, 1, 1, 1, 0, 0,0,1};
int length,i;
length=(sizeof(arr)/sizeof(*arr));
int indexCounter=0;
int sum=0;
for(i=0;i<length;i++)
{
if(arr[i]==1)
sum++;
else if(arr[i]==0)
sum–;

if(sum==0)
{
indexCounter=i+1;

}
}
cout<<"1 to "<<indexCounter;
return 0;
}

8. vikash mishra on August 26, 2014 at 7:27 pm said:

Best solution
TC =o(n); space =o(n)

1- create hash table.
2-for each element before storing in hash check if it is present in hash table then count_0++ or count_1++.
3- check if (count_0==count_1)
max = count_0;
flag=1;
4- try it for all elements
5-return max
6- start index= 0 and last index = max*2.

9. Ayush Sharma on August 30, 2014 at 9:05 am said:

meri book de ja bhai fir coding kar jam ke…

10. Filip Zivkovic on October 14, 2014 at 3:30 am said:

O(n) method that is really easy to understand:

Imagine you had a line chart. Every time there is a 1, you go one unit forward with a slope of 1. Every time there is a zero, you go one unit forward with a slope of -1. Now, any horizontal line you draw that crosses two points is a possible solution. So it is O(n) to make the chart, and O(1) to find the largest of the solutions.

To actually implement this, just use a counter, and check for two points where the counter is equal.

This is far better than the O(n^2) solution.

11. Anonymous on November 8, 2014 at 5:08 am said:

Actually it is working with your example. The solution is a dynamic programming.
In each step he uses the element for the set or not (the main loop)

12. Ramesh Babu Yagnam on November 8, 2014 at 9:01 am said:

public class MaxSizesubarray {

/**
* @param args
*/
public static void main(String[] args) {
MaxSizesubarray d = new MaxSizesubarray();
d.maxSubArrya(new int[]{1, -1, 1, 1, 1, -1, -1,-1,1});

}

public void maxSubArrya(int[] array) {
int maxSize = -1;
int i = 0;
int sum = -1;
int startingPoint=0;

for (i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j=j+2) {
sum = array[i] + sumSubArray(array, j, i);
if (sum == 0) {
if (maxSize < j) {
maxSize = j;
startingPoint =i;
}
}
}
}
System.out.println(startingPoint +" "+ maxSize);
}

public int sumSubArray(int[] a, int j, int i) {
int totalSunArraySum = 0;
while (j > i) {
totalSunArraySum = totalSunArraySum + a[j];

j–;
}

}

}

13. #include
int call(int[],int,int);
int i;
int main(void) {
int a[10],n;
scanf(“%d”,&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
call(a,0,n-1);

return 0;
}
int call(int a[],int i,int j)
{int k;
int count1,count0;
count1=count0=0;
for(k=i;k<=j;k++)
{if(a[k]==0)
count0++;
else
if(a[k]==1)
count1++;
}
if(count1==count0)
{printf(" i & j%d %d",i,j);
return 0;
}
call(a,i,j-1);
call(a,i+1,j);

}

14. VarunRam on March 20, 2015 at 4:43 pm said:

int main()
{
char arr[500] = “”;
char subStr[500] = “”;
int cnt = 0;
int cntIn = 0;
int sum = 0;
int maxLen = 0;

gets(arr);

while(arr[cnt])
{
cntIn = cnt;
sum = 0;
while(arr[cntIn])
{
sum += ((arr[cntIn] – 48) ? -1 : 1) ;
if(!sum && maxLen < (cntIn – cnt))
{
maxLen = cntIn – cnt;
strncpy(subStr, arr + cnt, cntIn – cnt + 1);
subStr[cntIn - cnt + 1] = '';

}
cntIn++;
}
cnt++;
}

if(maxLen)
{
printf("The biggest sub str is %s\n", subStr);
}

return 0;
}

try with giving all the possible ways

15. ankit bansal on June 26, 2015 at 11:16 pm said:

#include
#include
void main()
{
int a,c,b[100],i,n,counta=0,countc=0;
clrscr();
printf(“write the values of total elements”);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
a=1;
c=0;

for(i=1;icountc)
{
for(i=1;i<=countc;i++)
{
printf("1,0,");
}
}
else
{
for(i=1;i<=counta;i++)
{
printf("1,0,");
}
}

getch();
}

16. Vijyendra on June 27, 2015 at 11:52 am said:

String findLargestSubArray(int arr[], int n) {
int sum = 0;
int maxsize = -1, fromIndex = 0, endIndex = arr.length, reserveMaxsize = 0, reserveFromIndex =0;
int maxReserveEndIndex = 0;

// Pick a starting point as i
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0)
sum = -1;
else
sum = 1;
for (int j = i + 1; j < n; j++) {
if (arr[j] == 0)
sum += -1;
else
sum += 1;

if (sum == 0) {
endIndex = j;
maxsize = j -i +1;
fromIndex=i;
}
}
if(reserveMaxsize < maxsize){
reserveMaxsize = maxsize ;
reserveFromIndex = fromIndex;
maxReserveEndIndex = endIndex;
}
}
return "max Size…"+reserveMaxsize +" fromIndex… "+reserveFromIndex+ " endIndex…" + maxReserveEndIndex;
}

17. #include
using namespace std;

void processFromFront(int arr[], int size, int& lenF, int& startF, int& endF)
{
int aggArr[size][2];

for(int i=0;i<size;i++)
{
aggArr[i][0] = 0;
aggArr[i][1] = 0;
}
if(arr[0])
aggArr[0][1]++;
else
aggArr[0][0]++;

for(int i=1;i=0;i–)
{
if(!endF && aggArr[i][0] == aggArr[i][1])
{
lenF = 2*aggArr[i][1];
endF = i;
startF = lenF-endF-1;
break;
}
}
}

void processFromEnd(int arr[], int size, int& lenE, int& startE, int& endE)
{
int aggArr[size][2];

for(int i=size-1;i>=0;i–)
{
aggArr[i][0] = 0;
aggArr[i][1] = 0;
}

if(arr[size-1])
aggArr[size-1][1]++;
else
aggArr[size-1][0]++;

for(int i=size-2;i>=0;i–)
{
if(arr[i])
{
aggArr[i][1] = aggArr[i+1][1]+1;
aggArr[i][0] = aggArr[i+1][0];
}
else
{
aggArr[i][0] = aggArr[i+1][0]+1;
aggArr[i][1] = aggArr[i+1][1];
}
}
for(int i=0;i<size;i++)
{
if(!endE && aggArr[i][0] == aggArr[i][1])
{
lenE = 2*aggArr[i][1];
startE = i;
endE = startE+lenE-1;
break;
}
}
}

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

int lenF = 0, startF = 0, endF = 0;
int lenE = 0, startE = 0, endE = 0;

processFromFront(arr, size, lenF, startF, endF);
processFromEnd(arr, size, lenE, startE, endE);

system("PAUSE");
return 0;
}

Time Complexity – O(n)
Space COmplexity – O(n)