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)

Any better approach if you have, please do comments.

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. gopi on April 5, 2014 at 9:23 pm said:

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

  4. 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. Ankur on July 20, 2014 at 11:30 pm said:

    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. Mahesh on August 18, 2014 at 1:08 am said:

    #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–;
    }
    return totalSunArraySum;

    }

    }

  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;

    printf(“Please Enter the values\n”);

    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)

Leave a Reply to nikita Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation