Given an array of numbers, find an index such that the sum of numbers to the left is equal to the sum of elements to it’s right. If there are no elements to the left or right, the sum is considered to be zero.
This problem is from Hackerrank. Click here to solve this problem on your own.
A simple example will be {1,2,1}, at index 1, the left and right sum is 1.
This problem is from Hackerrank. Click here to solve this problem on your own.
A simple example will be {1,2,1}, at index 1, the left and right sum is 1.
One obvious approach to solve this problem can be as follows.
For each index, find the left sum and right sum and check if they are equal. This approach takes O(n2) time.
Let us look at some other method which uses some extra space to reduce the time complexity.
Build a prefix sum array which keeps track of the sum all the elements up to each index.
For the above example, the prefix sum array is {1,3,4}
The last element of this array indicates the sum of all elements in the original array.
Now, for each index i, we can find the left sum in prefix_sum[i-1] and right sum in total_sum – prefix_sum[i] which can be found in O(1) time. So this algorithm takes O(n) time.
Below Python/C++ code is provided which implements above.
The base cases are
- If the array contains zero elements, we cannot find such an index
- If the array has just one element, we can always find such an index.