Last Updated: 19 Nov, 2020
Equilibrium Index
Easy
Asked in companies
You are given an array Arr consisting of N integers. You need to find the equilibrium index of the array.
An index is considered as an equilibrium index if the sum of elements of the array to the left of that index is equal to the sum of elements to the right of it.
Note:
1. The array follows 0-based indexing, so you need to return the 0-based index of the element.
2. Note that the element at the equilibrium index won’t be considered for either left sum or right sum.
3. If there are multiple indices which satisfy the given condition, then return the left-most index i.e if there are indices i,j,k…. which are equilibrium indices, return the minimum among them
4. If no such index is present in the array, return -1.
Input Format:
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains the integer N, denoting the size of the array.
The second line of each test case contains N space-separated integers denoting the array elements.
Output Format:
The only line of output of each test case contains a single integer which corresponds to the equilibrium index for the array.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^5
-10^4 <= Arr[i] <= 10^4
Time Limit: 1 sec
Approaches
- We can try the brute force approach in which we consider every index starting from 0 as a possible candidate for equilibrium index, and to check if it is really an equilibrium index, we can calculate the sum of elements on both sides of that index, and check if they are equal or not. equal or not.
- Let us initialise the ans = -1, which will contain our valid index.
- Since index 0 and n - 1 cannot be possible candidates for the answer, we can start the loop from i = 1 to i = n - 2.
- Now for every i, let leftSum = 0 and rightSum = 0.
- For j = 0 to j = i - 1, do leftSum = leftSum + arr[j].
- For k = i + 1 to k = n - 1, do rightSum = rightSum + arr[k].
- If leftSum = rightSum, then return i.
- After the loop of i ends, return -1, since we have not found a valid index.
- Since we don’t want to calculate the sum of elements, again and again, we can store the sum of the elements in the form of prefix sums, because to check any index ‘i’, we are only interested in the sum of elements of the array up to ith index. Let prefSum[] be the array which stores the prefix sum, where prefSum[i] will be the sum of elements of the array up to the index i i.e prefSum[i] = arr[0] + arr[1] + …. + arr[i]
- So if we are at index i, the sum of elements to the left of index i is stored at leftSum = prefSum[i - 1], given that i-1 is a valid array index.
- Let arraySum denote the sum of the complete array.
- Now to find the sum of elements to the right of the index i, rightSum = total sum - (sum of elements to the left of i )+ arr[i](because we need to exclude the element at index i)
- The above statement can be simplified to rightSum = arraySum - prefSum[i - 1] + arr[i]. Thus we can say that rightSum = arraySum - prefSum[i] (since prefSum[i - 1] + arr[i] = prefSum[i]).
- If we get leftSum = rightSum at any index, return that index.
- After for loop ends return -1, since there is no valid index.
- We can even skip the prefix sum array and replace it with some variables. Consider the fact that when we are checking the index i to be equilibrium index, we are only interested in prefSum[i] and not any other value. This observation will help us to reduce the space complexity to O(1).
- Let arraySum be the sum of the array and leftSum = 0, which will denote the sum of elements to the left of index i.
- Now for i = 0 to i = n - 1, as we move from left to right do leftSum = leftSum + arr[i].
- The sum of elements to the right of i can be found as rightSum = arraySum - leftSum - arr[i].
- If we have leftSum = rightSum, then return i.
- After the loop is ended, return -1, since no such index exists.