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

A solution that's O(n) and doesn't require more space

def balance_array(arr):
    if len(arr) < 3:
        return False

    for i in range(1, len(arr)+1):
        lsum = sum(arr[:i])
        rsum = sum(arr[(i+1):])
        if lsum == rsum:
            return True
    return False

Testing

test_arrays = [[5, 3, 7, 0, 9], [5,2,3,1,4,6], [1,0,1], [1,6,5,1,2,3,1], [1,1], [], [1], [1,2,9,4,-1], [5, 4, 7, 0, 9], [1, -1, 1, 0, 1, -1, 1]]

for i in test_arrays:
    print(f'{i}\t{balance_array(i)}')

[5, 3, 7, 0, 9]         False
[5, 2, 3, 1, 4, 6]      True
[1, 0, 1]               True
[1, 6, 5, 1, 2, 3, 1]   True
[1, 1]                  False
[]                      False
[1]                     False
[1, 2, 9, 4, -1]        True
[5, 4, 7, 0, 9]         True
[1, -1, 1, 0, 1, -1, 1] True

Answer 2

You're looking for the centroid or center of mass. In pure Python:

def centroid(input_list):
    idx_val_sum = 0.0
    val_sum = 0.0
    for idx,val in enumerate(input_list):
        idx_val_sum += idx*val
        val_sum += val
    return idx_val_sum/float(val_sum)

It's O(n) and if non-integer results are ill-formed, you can reject them with a modulo check:

def integer_centroid(input_list):
    idx_val_sum = 0.0
    val_sum = 0.0
    for idx,val in enumerate(input_list):
        idx_val_sum += idx*val
        val_sum += val
    out = idx_val_sum/float(val_sum)
    if out%1.0==0.0:
        return out
    else:
        raise ValueError("Input list has non-integer centorid.")

This post should have been a comment replying to trumpetlicks June 14 2012 comment, but I don't have enough reputation. "Order" is implicitly tracked in idx_val_sum, which is the cumulative position sum weighted by value.

Edit:

Matt, thank you for your observation. I assumed this was a pseudocode question, but now I see the C++ tag. Here's some (untested) C++, with comments.

An intuitive example is a simple lever arm problem: if you have a lever with two forces f1 and f2 acting on it at positions x1 and x2, you can prevent the system from rotating by applying a force at position (f1*x1+f2*x2)/(f1+f2). A continuous system requires integration over the product of x and f, but levers with discrete locations and forces are a good analogy for this problem.

// untested code:

float centroid(float * vec, int vec_length){

  float idx_val_sum = 0.0;
  float val_sum = 0.0;

  for (idx = 0; idx < vec_length; idx++){

    // keep a running sum of the product of the index and the value
    idx_val_sum += float(idx)*vec[idx];

    // similarly, keep a running sum of the index
    val_sum += vec[idx];

  }
  // return the quotient of the product-sum and the index sum:
  return idx_val_sum/val_sum;
}

Answer 3

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 4

I believe you are looking for the Center of Mass, here is a solution written in Go:

func centerOfGravity(a []int) float64 {
  tot := 0.0
  mass := 0.0
  for i := range a {
    tot += float64(i) * float64(a[i])
    mass += float64(a[i])
  }
  return tot / mass
}

This gives you the index of the center of mass in the array, assuming a 0-based array. It can return a non-integer result since the center of mass can be anywhere in the range of the array.

Answer 5

I would actually have 2 start points, one on the leftmost point (leftLoc), and one at the right most point (rightLoc). Hold a sumLeft and sumRight numbers.

leftLoc  = 0;
rightLoc = (n - 1);
sumRight = array[rightLoc];
sumLeft  = array[leftLoc];

while(leftLoc < rightLoc){
    if(sumRight > sumLeft){
        leftLoc++;
        sumLeft += array[leftLoc];
    }else{
        rightLoc--;
        sumRight += array[rightLoc];
    } 
}

if( (sumRight + array[rightLoc - 1]) == sumLeft ){
    return rightLoc--;
}else if( (sumLeft + array[leftLoc + 1]) == sumRight){
    return leftLoc++;
}else{
    // return floating point number location in the middle of the 2 locations
}

All the while keeping track of how many total positions have been moved O(n)

You may find that your balance point is a floating point number in the middle of the final points (once they are at the integer locations right next to one another).

This should even work with the negative numbers example. Perhaps I am missing some fine grain details, but some variation on this theme should result you in an O(n) runtime algorithm.

Answer 6

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