An equilibrium index of a sequence as we know it is an index into the sequence such that the sum of elements at lower indices is equal to the sum of elements at higher indices.
For example, in a sequence A:
A{0}=-7
A{1}=1
A{2}=5
A{3}=2
A{4}=-4
A{5}=3
A{6}=0
- 3 is an equilibrium index because A{0}+A{1}+A{2}=A{4}+A{5}+A{6}
- 6 is also an equilibrium index because A{0}+A{1}+A{2}+A{3}+A{4}+A{5}=0 (sum of zero elements is zero)
- 7 is not an equilibrium index, because it is not a valid index of sequence A.
In other words, for a better explanation; equilibrium index of an array is an index i such that the sum of elements at indices less than i is equal to the sum of elements at indices greater than i. Element at index i is not included in either part as we know that and it is stated that if more than one equilibrium index is present, you need to return the first one. Also, return -1 if no equilibrium index is present.
We can very well take an example here, in this program to find the equilibrium index of an array is discussed here. Equilibrium index of an array is an index such that:
Sum of elements at lower indexes = Sum of elements at higher indexes.
For example, consider the array a[] = {-7, 1, 5, 2, -4, 3, 0}.
Here, a[0] + a[1] + a[2] = a[4] + a[5] + a[6].
Hence, 3 is the equilibrium index.
Method 1: (Simple but inefficient) Use two loops, outer loop iterates through all the element and inner loop find out whether the current index picked by the outer loop is equilibrium index or not. The time complexity of this solution is O(n^2) for which we will later give an explanation also. A straightforward method is to use two loops. The idea is to find the sum of elements for every range of indexes and observe if there exists an equilibrium index. The outer loop traverses the array and the inner loop determines if there is an equilibrium index or not.
- Using two loops
- Outer loop iterates through all the element and the inner loop check out whether the current index picked by the outer loop is either equilibrium index or not.
- Run a loop through the array
- For each index, find the sum of elements towards the left and right of the current index
- If the left_sum and right_sum are equal, then the current index is the equilibrium index
- Otherwise, return -1
- The time complexity of this solution is O(n^2)
Program Code:
// C program to find the equilibrium index of an array
#include
int equilibrium_index(int arr[], int n)
{
int i, j;
int leftsum, rightsum;
for (i = 0; i < n; ++i) {
leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];
rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];
if (leftsum == rightsum)
return i;
}
return -1;
}
int main()
{
int n;
printf(“\nEnter the number of elements : “);
scanf(“%d”,&n);
int arr[n];
printf(“\nInput the array elements : “);
for(int i = 0; i < n; i++)
{
scanf(“%d”,&arr[i]);
}
printf(“\nEquilibrium Index : %d\n”, equilibrium_index(arr, n));
return 0;
}
// End of program
Output:
Enter the number of elements: 7
Input the array elements : 1 2 3 4 1 2 3
Equilibrium index : 3
Time complexity: O(n^2)
The major reason to make and identify this method as inefficient is its time complexity.
Method 2: (Tricky and efficient): Find the sum of the array and then traverse through the array and keep
updating the left sum which is initially zero. To get the right sum, subtract the array values from the sum while traversing. Check the left sum and right sum at each step. If they are equal, return the current index.
The idea is to get the total sum of the array first. Then iterate through the array and keep updating the left sum which is initialised as zero. In the loop, we can get the right sum by subtracting the elements one by one. Basically store the prefix sum of the array. The prefix sum would help keep track of the sum of all elements up to any index of the array. Now, we should find a way to keep track of the sum of values to the right of the current index.
We can use a temporary sum variable, which initially stores the sum of all elements of the array. If we subtract the value at the current index, we will get the sum of values to the right. Now, compare both left_sum and right_sum to find whether the current index is the equilibrium index or not.
Algorithm:
- Initialise left_sum = 0
- Find the sum of the array as a sum
- For i = 1 to end of the array, do the following
- Update sum to get the right sum
- sum = sum – arr[i] // sum is the right sum
- If left_sum == sum, return current index
- Update left_sum = left_sum + arr[i]
- Return -1 and exit the algorithm. // Equilibrium index is not found
Programme Code:
#include<stdio.h>
int equilibrium_index(int arr[], int n)
{
int sum = 0;
int leftsum = 0;
for (int i = 0; i < n; ++i)
sum += arr[i];
for (int i = 0; i < n; ++i) {
sum -= arr[i];
if (leftsum == sum)
return i;
leftsum += arr[i];
}
return -1;
}
int main()
{
int n;
printf(“\nEnter the number of elements : “);
scanf(“%d”,&n);
int arr[n];
printf(“\nInput the array elements : “);
for(int i = 0; i < n; i++)
{
scanf(“%d”,&arr[i]);
}
printf(“\nEquilibrium Index : %d\n”, equilibrium_index(arr, n));
return 0;
}
// End of program
Output:
Enter the number of elements: 7
Input the array elements : 1 2 3 4 1 2 3
Equilibrium index: 3
Time complexity: O(n)
As it is known well, we can remove the return statement and add a print statement to print all equilibrium indexes instead of returning only one. We are running two separate loops for calculating the prefix sum array
and equilibrium index respectively. Time Complexity = Time complexity of calculating prefix sum array +
Time complexity of calculating Equilibrium Index = O(n) + O(n) = O(n) Space Complexity: The above algorithm uses extra space to create a prefix sum array. Hence, the space complexity would be O(n).
From this, we know that there are other better methods also, so here we will be exploring some of them:
- Naive Solution: Naive approach to calculate the sum of elements to the left and sum of elements to the right as we define that. If the left sub-array sum is the same as the right sub-array sum for an element, we print its index. The time complexity of the above solution is O(n).
- Linear Time Solution: We can solve this problem in linear time by using extra space. The idea is to create an auxiliary array left[] were left[i] stores sum of elements of sub-array A[o..i-1]. After the letter 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]s 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. The time complexity of the above solution is O(n) and auxiliary space used by the program is O(n).
- Optimised Solution: The motive is to get the total sum of the array first. The difference between the above method and this method is that we don’t need to store the prefix sum beforehand. Instead, we will keep track of the left_sum while traversing the array itself. In the loop, we can get the right_sum by subtracting the elements one by one. 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 the total sum that is:
Sum of left subarray A[0..i-1] = total – (A[i] + sum of right subarray A[i+1..n-1]).
We are running two separate loops for calculating the total sum and equilibrium index respectively.
Time complexity = Time complexity of calculating prefix sum array + Time complexity of calculating Equilibrium Index = O(n) + O(n) = O(n) Space Complexity = O(1), because we are just using variables to store the value of total, left, and the right sum.
The time complexity of the above solution is O(n) and auxiliary space used by the program is O(1).
Hope you have gained enough knowledge from this article! Thanks for reading so far, stay tuned for more!
To explore our courses, click here.
By Deepak Jain
