Space-efficient algorithm for finding the largest balanced subarray?

given an array of 0s and 1s, find maximum subarray such that number of zeros and 1s are equal. This needs to be done in O(n) time and O(1) space.

I have an algo which does it in O(n) time and O(n) space. It uses a prefix sum array and exploits the fact that if the number of 0s and 1s are same then sumOfSubarray = lengthOfSubarray/2

#include<iostream>
#define M 15

using namespace std;

void getSum(int arr[],int prefixsum[],int size) {
    int i;
    prefixsum[0]=arr[0]=0;
    prefixsum[1]=arr[1];
    for (i=2;i<=size;i++) {
        prefixsum[i]=prefixsum[i-1]+arr[i];
    }
}

void find(int a[],int &start,int &end) {
    while(start < end) {
        int mid = (start +end )/2;
        if((end-start+1) == 2 * (a[end] - a[start-1]))
                break;
        if((end-start+1) > 2 * (a[end] - a[start-1])) {
            if(a[start]==0 && a[end]==1)
                    start++; else
                    end--;
        } else {
            if(a[start]==1 && a[end]==0)
                    start++; else
                    end--;
        }
    }
}

int main() {
    int size,arr[M],ps[M],start=1,end,width;
    ;
    cin>>size;
    arr[0]=0;
    end=size;
    for (int i=1;i<=size;i++)
            cin>>arr[i];
    getSum(arr,ps,size);
    find(ps,start,end);
    if(start!=end)
            cout<<(start-1)<<" "<<(end-1)<<endl; else cout<<"No soln\n";
    return 0;
}

arrays algorithm binary-data

Edit Report

I would argue that it is impossible, that an algorithm with O(1) exists, in the following way. Assume you iterate ONCE over every bit. This requires a counter which needs the space of O(log n). Possibly one could argue that n itself is part of the problem instance, then you have as input length for a binary string of the length k: k + 2-log k. Regardless how you look over them you need an additional variable, on case you need an index into that array, that already makes it non O(1).

Usually you dont have this problem, because you have for an problem of the size n, an input of n numbers of the size log k, which adds up to nlog k. Here a variable of length log k is just O(1). But here our log k is just 1. So we can only introduce a help variable that has constant length (and I mean really constant, it must be limited regardless how big the n is).

Here one problem is the description of the problem comes visible. In computer theory you have to be very careful about your encoding. E.g. you can make NP problems polynomial if you switch to unary encoding (because then input size is exponential bigger than in a n-ary (n>1) encoding.

As for n the input has just the size 2-log n, one must be careful. When you speak in this case of O(n) - this is really an algorithm that is O(2^n) (This is no point we need to discuss about - because one can argue whether the n itself is part of the description or not).

answered 2011-09-15T14:52:51.003

Space-efficient algorithm for finding the largest balanced subarray?

1 Answer

Your Answer