Equilibrium indices of a Sequence

PROBLEM STATEMENT

You have been given an array/list 'SEQUENCE' denoting the sequence of 'N' integers. Your task is to find the equilibrium indices of the sequence in 'SEQUENCE'.

The equilibrium index of a sequence of integers is defined as the index such that the sum of all the elements at lower indices is equal to the sum of elements at higher indices.

Note:

1. 'SEQUENCE' may contain more than one equilibrium indices.

2. If there are no equilibrium indices, return an empty sequence.

3. Consider the sum of elements lower than the first index and higher than the last index to be 0 (zero).

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the given array/list 'SEQUENCE'. 

The second line of each test case contains ‘N’ space-separated integers denoting the elements in the 'SEQUENCE'.

Output Format:

For each test case, return a sequence of equilibrium indices. If no such index exists, return an empty sequence.

Note:

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^4
-10^9 <= SEQUENCE[i] <= 10^9

Where 'SEQUENCE[i]' denotes the elements of the array 'SEQUENCE'.

Time limit: 1 sec

Approach 1

For an index to be at equilibrium we need to calculate the sum of all the elements present at indices lower than the index and the sum of all the elements present at indices higher than the index. If both the sums match then we can add that index to the sequence of equilibrium indices. Hence, for a given sequence we can iterate through each of the indexes and store it as ‘currentIndex’.

Now iterate through all the elements present at indices lower than ‘currentIndex’ and store it as ‘lowerSum’. Similarly, iterate through all the elements present at indices higher than ‘currentIndex’ and store it as ‘higherSum’. If ‘lowerSum’ matches ‘higherSum’ than the ‘currentIndex’ is at equilibrium and we add it to the answer sequence, else we traverse further in the sequence.

Once we complete the traversal we can return the answer sequence, which contains all the equilibrium indices or empty sequence in case of no equilibrium indices.

Try Problem

Approach 2

What if we store the sum of all elements before every index and sum of all elements after every index then we can check if an element is an equilibrium element in a very efficient way. We can use the prefix sum array and suffix sum array to implement the idea.

Following is a detailed approach for the same:

Create 2 arrays named ‘prefixSum’ and ‘suffixSum’ each of size ‘N’.
‘prefixSum[i]’ where ‘i’ is the current index, stores the sum of all elements which have an index less than or equal to ‘i’.
‘suffixSum[i]’ where ‘i’ is the current index, stores the sum of all elements which have an index greater than or equal to ‘i’.
For the special case when we are at the first(‘i=0’) or last index(‘i=n-1’), we simply check if ‘suffixSum[0]’ is 0 for the first index and if ‘prefixSum[n-1]’ is 0 for the last index.
For all other indices, we check if the ‘prefixSum[i-1]’ is equal to the ‘suffixSum[i+1]’ and if it is true we add it to the answer sequence.
Finally, we return the answer sequence.

Try Problem

Approach 3

Firstly, we can traverse the complete sequence of elements and calculate the total sum. We can store the total sum as ‘totalSum’. Create 2 variables ‘leftSum’ and ‘rightSum’. Initialize ‘leftSum’=0 and ‘rightSum’= ‘totalSum’.

Then iterate through the sequence and do the following:

While traversing through the indices subtract the elements at the current index from ‘leftSum’ .
If for any index, the ‘leftSum’ is equal to ‘rightsum’, we add that index as the equilibrium index in the answer sequence.
Add the element at the current index to ‘leftSum’ before checking for the next index.

Finally, return the answer sequence formed.

Try Problem