Home » Technical Interview Questions » Array Interview Questions » Largest subarray with equal number of 0’s and 1’s

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


Reading Time - 3 mins

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

READ  Find Three Element From Different Three Arrays Such That a + b + c = sum

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.

READ  Three way partitioning of an array around a given range

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions