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

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

  1. Simply run two loops, Initialize sum =0
  2. Pick each element in the outer loop ie, i=0 to n
  3. The inner loop will select all the elements starting from outerloop element ie, j=i+1 to n
  4. In the outerloop, if the element ie, arr[i] is 0 then make sum = -1 else, make sum = 1.
  5. In the inner loop, if the element ie, arr[j] is 0 then make sum = sum - 1 else, make sum = sum + 1
  6. 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
  7. 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;
}
Try It

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;
}
Try It


Next > < Prev
Scroll to Top