Find equilibrium index of an array

Given an array of integers, find equilibrium index in it.

 

For an array A consisting n elements, index i is an equilibrium index if sum of elements of sub-array A[0..i-1] is equal to the sum of elements of sub-array A[i+1..n-1] i.e.

(A[0] + A[1] + . . . + A[i-1]) = (A[i+1] + A[i+2] + . . . + A[n-1])   where 0 < i < n-1

Similarly, 0 is an equilibrium index if (A[1] + A[2] + . . . + A[n-1]) = 0 and
n-1 is an equilibrium index if (A[0] + A[1] + . . . + A[n-2]) = 0

 
For example, consider the array {0, -3, 5, -4, -2, 3, 1, 0}. The equilibrium index found at index 0, 3 and 7.

 


 

Naive approach is to calculate sum of elements to the left and sum of elements to the right for each element of the array. If left sub-array sum is same as right sub-array sum for an element, we print its index. The time complexity of above solution is O(n2).

 

We can solve this problem in linear time by using extra space. The idea is to create an auxiliary array left[] where left[i] stores sum of elements of sub-array A[0..i-1]. After left[] is filled, we traverse the array from right to left and update right sub-array sum for each element encountered. Now if sum of elements of left sub-array A[0..i-1] is equal to the sum of elements of right sub-array A[i+1..n) for element A[i], we have found equilibrium index at i.

C++

Download   Run Code

Java

Download   Run Code



Output:

Equilibrium Index found at 7, 3 and 0

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 
Optimized solution -
 

We can avoid using extra space. The idea is to calculate the sum of all elements of the array. Then we start from the last element of the array and maintain right sub-array sum. We can calculate left sub-array sum in constant time by subtracting right sub-array sum and current element from total sum. i.e.


Sum of left subarray A[0..i-1] = total - (A[i] + sum of right subarray A[i+1..n-1])

C++

Download   Run Code

Java

Download   Run Code



Output:

Equilibrium Index found at 7, 3 and 0

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Exercise:
Find an element in the array before which all the elements are smaller and after which all are greater.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


    

  • hcg2007

    According to the description “(A[0] + A[1] + . . . + A[i-1]) = (A[i+1] + A[i+2] + . . . + A[n-1])”, 0 and n-1 are not valid indexes because A[i-1] and A[i+1] are not valid.

    • Techie Delight

      Thanks for correcting. We have updated the problem description. Please let us know if you find any more issues. Happy coding!