## Given an array, this function will find the largest subarray with equal number of 0’s and 1’s and will print the start index and end index of the largest subarray

### Example

**INPUT:**

arr[] = {1, 1, 0, 1, 0}

OUTPUT:

index 1 to index 4

**Time Complexity: O()**

In this method, we will assume all the zeroes to be -1

## Algorithm

- Simply run two loops, Initialize sum =0
- Pick each element in the outer loop ie, i=0 to n
- The inner loop will select all the elements starting from outerloop element ie, j=i+1 to n
- In the outerloop, if the element ie, arr[i] is 0 then make sum = -1 else, make sum = 1.
- In the inner loop, if the element ie, arr[j] is 0 then make sum = sum – 1 else, make sum = sum + 1
- check if the sum is equal to zero and present subarray size ie, j – i +1 is greater than maximum size. if yes, update the maximum size and store the start index of the subarray
- print the subarray indexes using start index and subarray size

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
void largestSubarray(int arr[], int n)
{
int maxsize = -1; //to upddate the maximum size of subarray
int start_index = 0;
for (int i = 0; i < n-1; ++i)
{
int sum = 0;
if(arr[i] == 0) //considering all zeroes as -1
{
sum = -1;
}
else
{
sum = 1;
}
for (int j = i+1; j < n; ++j)
{
if(arr[j]==0)
{
sum = sum - 1; //finding sum of the subarray
}
else
{
sum = sum + 1;
}
if(sum == 0 && (j - i +1) > maxsize )
{
maxsize = j-i+1;
start_index = i;
}
}
}
cout<<"Start index is "<<start_index<<" and ";
cout<<"End index is "<<maxsize + start_index -1<<endl;
for (int i = start_index; i <= (start_index + maxsize -1); ++i)
{
cout<<arr[i]<<" ";
}
}
int main()
{
int arr[]= {1, 1, 0, 1, 0}; //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
largestSubarray(arr, n);
return 0;
}
```

**Time Complexity: O(n)**

## Algorithm

**1.** Consider all zeroes as -1, now we need to find the largest subarray with sum 0.

**2.** Create a new temporary array, which stores the sum from start element to the present element ie, temp[i]

**3.** Now, look for i, j such that temp[i] ==temp[j]. Because, if those elements are same then the sum of middle elements in given array is 0 ie,equal 0’s 1’s

Now, we have two cases.

**Case 1:**

**i)** If the output subarray start from the index 0 ie temp[i] =0, then return maximum value of i

**Case 2:**

**i)** If the output array did not start from index 0, we will find i, j such that temp[i] == temp[j] and j-i is maximum

** ii)** To solve this, we will create a hash table to store the first occurrence of that number ie, int hash[max-min+1] where min is the minimum value in temp array and max is the maximum value in temp array

**iii)** Traverse the temp array, hash array contains only positive indexes so,take value = temp[i] – min

**a.** if the value is not present in hash table ie, hash[value] = -1 then we do hash[value] =index,

that is storing the left most occurrence of that value

**b.** If the value is already present in hash[], we check

if(current index – hash[value] > max length ), then update maxlength and start index

ie, max length = current index – hash[value]

start index = hash[value] + 1

**4.** If the maxlength doesnt get updated then there is no such subarray with same 0’s, 1’s.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
void largestSubarray(int arr[], int n)
{
int maxlength = -1; //to upddate the maximum size of subarray
int start_index = 0;
int temp[n];
int min = arr[0], max = arr[0];
if (arr[0]==0)
{
temp[0]=-1;
}
else
{
temp[0]=1;
}
for (int i = 1; i < n; ++i)//creating temp array
{
if (arr[i]==0)
{
temp[i] = temp[i-1] - 1; //adding all the elements that are left
}
else
{
temp[i] = temp[i-1] + 1;
}
if(temp[i]<min)
min = temp[i];
if(temp[i]>max)
max = temp[i];
}
int hash[max-min+1];
// Initialize hash table
for (int i=0; i<max-min+1; i++)
hash[i] = -1;
for (int i = 0; i < n; ++i)
{
//case 1
if (temp[i]==0)
{
maxlength = i + 1;
start_index = 0;
}
//case 2
if (hash[temp[i]-min] == -1)//value is not present in table
{
hash[temp[i]-min] = i; //storing the index of left occurence of the value
}
else
{
if ((i - hash[temp[i]-min]) > maxlength)//check current subarray length with max length
{
maxlength = i - hash[temp[i]-min];
start_index = hash[temp[i]-min] + 1;
}
}
}
if(maxlength == -1)
{
cout<<"No subarray has eqaul number of 0's, 1's"<<endl;
}
else
{
cout<<"Start index is "<<start_index<<" and ";
cout<<"End index is "<<maxlength + start_index -1<<endl;
for (int i = start_index; i <= (start_index + maxlength -1); ++i)
{
cout<<arr[i]<<" ";
}
}
}
int main()
{
int arr[]= {1,1,0,1,0}; //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
largestSubarray(arr, n);
return 0;
}
```