Finding the balance point in an array

Question

This question is from a great youtube channel, giving problems that can be asked in interviews.

It's basically related to finding the balance point in an array. Here is an example to best explain it; {1,2,9,4,-1}. In here since sum(1+2)=sum(4+(-1)) making the 9 the balance point. Without checking the answer I've decided to implement the algorithm before wanted to ask whether a more efficient approach could be done;

1. Sum all the elements in array O(n)
2. Get the half of the sum O(1)
3. Start scanning the array, from left, and stop when the sumleft is bigger than half of the general sum. O(n)
4. Do the same for the right, to obtain sum right. O(n).
5. If sumleft is equal to sumright return arr[size/2] else return -1

I'm asking because this solution popped into my head without any effort, providing the O(n) running time. Is this solution, if true, could be developed or if not true any alternative methods?

Answer 1

Your algorithm is not good (counter-example: 1 -1 1 0 1 -1 1), the good solution is to compute partial sum of your array (so that you can can compute sumleft and sumright in O(1) for each cell of the array) and then (or in the same time if you already know the global sum) search in your array a cell such that sumleft = sumright which is O(n).

The partial sum of the array A is

[A[0], A[0]+A[1], A[0]+A[1]+A[2], …, A[0]+A[1]+A[2]+…+A[n-1]]

example:

A=[5,2,3,1,4,6]
partial sum = [5,7,10,11,15,21]

With this array you can compute sumleft[i]=partial_sum[i-1] and sumright[i]=partial_sum[n-1]-partial_sum[i]

Improvement:

Computing the global sum first and then only the partial sum for the current index enable you to use only O(1) extra space instead of O(n) extra space if you store all the partial_sum array.

Answer 2

Basically add up all the numbers first. This will be an O(n) operation. Then substract one element from the array at a time starting from the beginning of the array till upper == lower. Thus the total order will be O(n).

int BalancePoint(int a[], int begin, int end) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1
{
    if(!a) return -1;
    else if(begin == end) return begin;

        long long upper = 0;
        long long lower = 0;

    for(int i = begin; i <= end; ++i)
    {
        upper += *(a+i);
    }

    for(int j = begin; j <= end; ++j)
    {
        upper -= *(a+j);
        if(upper == lower) return j;
        lower += *(a+j);
    }
    return -1;
}

Using STL

int BalancePointSTL( const vector<int> &A ) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1
{
    if(A.empty()) return -1;

        long long upper = 0;
        long long lower = 0;

    for(unsigned int i = 0; i <= A.size(); ++i)
    {
        upper += A[i];
    }

    for(unsigned int j = 0; j < A.size(); ++j)
    {
        upper -= A[j];
        if(upper == lower) return j;
        lower += A[j];
    }
    return -1;
    }

The following would have a better worst case performance but a couple more if-else comparisons

int BalancePoint2(int a[], int begin, int end) // Better worst case senario by factor of 2
{
    if(!a) return -1;
    else if(begin == end) return begin;

        long long upper = 0;
        long long lower = 0;

        int mid = (end-begin)/2;

        for(int i = begin; i < mid; ++i)
        {
            lower += *(a+i);
        }
        for(int i = mid+1; i <= end; ++i)
        {
            upper += *(a+i);
        } 

        if(upper == lower) return mid;
        else if(lower < upper)
        {
            lower += *(a+mid);
            for(int i= mid + 1 ; i <= end ; ++i)
            {
                upper -= *(a + i);
                if(upper == lower) return i;
                lower += *(a + i);
            }
        }
        else {
            upper += *(a + mid);
            for(int i = mid - 1; i >=begin; --i)
            {
                lower -= *(a + i);
                if(upper == lower) return i;
                upper += *(a + i);
            }
        }
        return -1;
}