Finding the balance point in an array
algorithm, c++, data-structures, performance
Solution
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.
Problem
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; - Sum all the elements in array O(n) - Get the half of the sum O(1) - Start scanning the array, from left, and stop when the sumleft is bigger than half of the general sum. O(n) - Do the same for the right, to obtain sum right. O(n). - 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?