Space-efficient algorithm for finding the largest balanced subarray?

Question

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

Answer 1

Now my algorithm is O(n) time and O(Dn) space where Dn is the total imblance in the list.

This solution doesn't modify the list.

let D be the difference of 1s and 0s found in the list.

First, let's step linearily through the list and calculate D, just to see how it works:

I'm gonna use this list as an example : l=1100111100001110

Element   D null      0 1         1 1         2   <- 0         1 0         0 1         1 1         2 1         3 1         4 0         3 0         2 0         1 0         0 1         1 1         2 1         3 0         2   <- 

Finding the longest balanced subarray is equivalent to finding 2 equal elements in D that are the more far appart. (in this example the 2 2s marked with arrows.)

The longest balanced subarray is between first occurence of element +1 and last occurence of element. (first arrow +1 and last arrow : 00111100001110)

Remark:

The longest subarray will always be between 2 elements of D that are between [0,Dn] where Dn is the last element of D. (Dn = 2 in the previous example) Dn is the total imbalance between 1s and 0s in the list. (or [Dn,0] if Dn is negative)

In this example it means that I don't need to "look" at 3s or 4s

Proof:

Let Dn > 0 .

If there is a subarray delimited by P (P > Dn). Since 0 < Dn < P, before reaching the first element of D which is equal to P we reach one element equal to Dn. Thus, since the last element of the list is equal to Dn, there is a longest subarray delimited by Dns than the one delimited by Ps.And therefore we don't need to look at Ps

P cannot be less than 0 for the same reasons

the proof is the same for Dn <0

Now let's work on D, D isn't random, the difference between 2 consecutive element is always 1 or -1. Ans there is an easy bijection between D and the initial list. Therefore I have 2 solutions for this problem:

• the first one is to keep track of first and last appearance of each element in D that are between 0 and Dn (cf remark).
• second is to transform the list into D, and then work on D.

---

FIRST SOLUTION

For the time being I cannot find a better approach than the first one:

First calculate Dn (in O(n)) . Dn=2

Second instead of creating D, create a dictionnary where the keys are the value of D (between [0 and Dn]) and the value of each keys is a couple (a,b) where a is the first occurence of the key and b the last.

Element   D DICTIONNARY null      0 {0:(0,0)} 1         1 {0:(0,0) 1:(1,1)} 1         2 {0:(0,0) 1:(1,1) 2:(2,2)} 0         1 {0:(0,0) 1:(1,3) 2:(2,2)} 0         0 {0:(0,4) 1:(1,3) 2:(2,2)} 1         1 {0:(0,4) 1:(1,5) 2:(2,2)} 1         2 {0:(0,4) 1:(1,5) 2:(2,6)} 1         3 { 0:(0,4) 1:(1,5) 2:(2,6)} 1         4 {0:(0,4) 1:(1,5) 2:(2,6)}   0         3{0:(0,4) 1:(1,5) 2:(2,6) } 0         2 {0:(0,4) 1:(1,5) 2:(2,9) } 0         1 {0:(0,4) 1:(1,10) 2:(2,9) }  0         0 {0:(0,11) 1:(1,10) 2:(2,9) }  1         1 {0:(0,11) 1:(1,12) 2:(2,9) }  1         2 {0:(0,11) 1:(1,12) 2:(2,13)} 1         3 {0:(0,11) 1:(1,12) 2:(2,13)}  0         2 {0:(0,11) 1:(1,12) 2:(2,15)}  

and you chose the element with the largest difference : 2:(2,15) and is l[3:15]=00111100001110 (with l=1100111100001110).

Time complexity :

2 passes, the first one to caclulate Dn, the second one to build the dictionnary. find the max in the dictionnary.

Total is O(n)

Space complexity:

the current element in D : O(1) the dictionnary O(Dn)

I don't take 3 and 4 in the dictionnary because of the remark

The complexity is O(n) time and O(Dn) space (in average case Dn << n).

I guess there is may be a better way than a dictionnary for this approach.

Any suggestion is welcome.

Hope it helps

---

SECOND SOLUTION (JUST AN IDEA NOT THE REAL SOLUTION)

The second way to proceed would be to transform your list into D. (since it's easy to go back from D to the list it's ok). (O(n) time and O(1) space, since I transform the list in place, even though it might not be a "valid" O(1) )

Then from D you need to find the 2 equal element that are the more far appart.

it looks like finding the longest cycle in a linked list, A modification of Richard Brent algorithm might return the longest cycle but I don't know how to do it, and it would take O(n) time and O(1) space.

Once you find the longest cycle, go back to the first list and print it.

This algorithm would take O(n) time and O(1) space complexity.

Answer 2

Different approach but still O(n) time and memory. Start with Neil's suggestion, treat 0 as -1.

Notation: A[0, …, N-1] - your array of size N, f(0)=0, f(x)=A[x-1]+f(x-1) - a function

If you'd plot f, you'll see, that what you look for are points for which f(m)=f(n), m=n-2k where k-positive natural. More precisely, only for x such that A[x]!=A[x+1] (and the last element in an array) you must check whether f(x) already occurred. Unfortunately, now I see no improvement over having array B[-N+1…N-1] where such information would be stored.

To complete my thought: B[x]=-1 initially, B[x]=p when p = min k: f(k)=x . And the algorithm is (double-check it, as I'm very tired):

fx = 0 B = new array[-N+1, …, N-1] maxlen = 0 B[0]=0 for i=1…N-1 :     fx = fx + A[i-1]     if B[fx]==-1 :         B[fx]=i     else if ((i==N-1) or (A[i-1]!=A[i])) and (maxlen < i-B[fx]):         We found that A[B[fx], …, i] is best than what we found so far         maxlen = i-B[fx] 

---

Edit: Two bed-thoughts (= figured out while laying in bed :P ):

1) You could binary search the result by the length of subarray, which would give O(n log n) time and O(1) memory algorithm. Let's use function g(x)=x - x mod 2 (because subarrays which sum to 0 are always of even length). Start by checking, if the whole array sums to 0. If yes -- we're done, otherwise continue. We now assume 0 as starting point (we know there's subarray of such length and "summing-to-zero property") and g(N-1) as ending point (we know there's no such subarray). Let's do

    a = 0     b = g(N-1)     while a<b :          c = g((a+b)/2)         check if there is such subarray in O(n) time         if yes:             a = c         if no:             b = c     return the result: a (length of maximum subarray) 

Checking for subarray with "summing-to-zero property" of some given length L is simple:

    a = 0     b = L     fa = fb = 0     for i=0…L-1:         fb = fb + A[i]     while (fa != fb) and (b<N) :         fa = fa + A[a]         fb = fb + A[b]         a = a + 1         b = b + 1     if b==N:         not found     found, starts at a and stops at b 

2) …can you modify input array? If yes and if O(1) memory means exactly, that you use no additional space (except for constant number of elements), then just store your prefix table values in your input array. No more space used (except for some variables) :D

And again, double check my algorithms as I'm veeery tired and could've done off-by-one errors.