Find equilibrium Index of an Array
Equilibrium Index of an Array
The purpose of this post is to explain and find equilibrium index of an array with n elements. For an array arr consisting of n elements, index i is an equilibrium index if the sum of elements of subarray arr[0…i-1] is equal to the sum of elements of subarray arr[i+1…n-1]. i.e. (arr[0] + arr[1] + … + arr[i-1]) = (arr[i+1] + arr[i+2] + … + arr[n-1]) where 0 < i < n-1. Similarly, 0 is an equilibrium index if arr[1] + arr[2] + … arr[n-1] sums to 0 and n-1 is an equilibrium index if arr[0] + arr[1] + … + arr[n-2] sums to 0.
To illustrate, consider the array {0, -3, 5, -4, -2, 3, 1, 0}. The equilibrium index is found at index 0, 3, and 7.
Linear-Time Solution
This solution to the above problem is in linear time and uses extra space. The idea is to create an auxiliary array left[] were left[i] stores a sum of elements of the subarray arr[0…i-1]. After left[] is filled, traverse the array from right to left and update them right subarray sum for each element encountered.
Now, if the sum of elements of the left subarray arr[0…i-1] is equal to the sum of elements of the right subarray arr[i+1…n-1] for element arr[i]. we have found the equilibrium index at i. Implementation of the above approach in C++, Java, and Python is provided below:
Program of find equilibrium Index of an Array in C++
// Program to find equilibrium index
// in linear time by using extra space
#include<iostream>
// function definition
void equilibriumIndex(int arr[], int size){
// left[i] stores the sum of elements of the subarray arr[0...i-1]
int left[size];
left[0]=0;
// loops from index 1 to size-1
for(int i=1;i<size;i++){
left[i]=left[i-1]+arr[i-1];
}
// stores sum of right subarray arr[i+1...size-1]
int right=0;
std::cout<<"Equilibrium indeices are: \n";
// traversing from the end
for(int i=size-1;i>=0;i--){
if(left[i]==right){
std::cout<<i<<" ";
}
right+=arr[i];
}
}
int main(){
int arr[]={0,-3,5,-4,-2,3,1,0};
int size=sizeof(arr)/sizeof(arr[0]);
// function call to equilibriumIndex()
equilibriumIndex(arr,size);
}
Output:
Equilibrium indeices are: 7 3 0
Program of find equilibrium Index of an Array in Java
// Program to find equilibrium index of an array
// in linear time by using extra space
public class equilibrium_index {
static void equilibriumIndex(int arr[]){
// size of arr
int size=arr.length;
// left[i] stores sum of elements of subarray arr[0...i-1]
int[] left=new int[size];
left[0]=0;
for(int i=1;i<size;i++){
left[i]=left[i-1]+arr[i-1];
}
// stores sum of right subarray arr[i+1...size-1]
int right=0;
System.out.println("Equilibrium indices: ");
for(int i=size-1;i>=0;i--){
if(right==left[i]){
System.out.print(i+" ");
}
right+=arr[i];
}
}
public static void main(String[] args) {
int arr[]={0,-3,5,-4,-2,3,1,0};
equilibriumIndex(arr);
}
}
Output:
Equilibrium indices: 7 3 0
Program of find equilibrium Index of an Array in Python
# Program to find equilibrium index of an array
# in linear time by using extra space
# function definition
def equilibriumIndex(arr):
# stores length of array arr
size=len(arr)
# left[i] stores sum of elements of subarray arr[0...i-1]
left=[0]*size
for i in range(1,size):
left[i]=left[i-1]+arr[i-1]
# stores sum of subarray arr[i+1...size-1]
right=0
print("equilibrium Indices: ")
for i in range(size-1,-1,-1):
if right==left[i]:
print(i,end=" ")
right+=arr[i]
arr=[0, -3, 5, -4, -2, 3, 1, 0]
equilibriumIndex(arr)
Output:
equilibrium Indices: 7 3 0
The time complexity of the above linear-time solution is O(n) and requires O(n) extra space, where n is the input size of the array.
Optimized Solution
The use of extra space can be avoided. This can be done by calculating the sum of all the array elements. Then, start from the last item of the array and maintain the right subarray sum. We then calculate the left subarray sum in constant time by subtracting the right subarray sum and current element from the total sum, i.e.,
Sum of left subarray arr[0…i-1] = total_sum – (arr[i] + sum of right subarray arr[i+1…n-1])
Implementation of the above approach in C++, Java, and Python is given below:
In C++
// Program to find equilibrium index
// in linear time
#include<iostream>
// contains accumulate function which adds elements of a range
#include<numeric>
void equilibriumIndex(int arr[], int size){
int total_sum=std::accumulate(arr,arr+size,0);
// stores sum of right subarray
int right=0;
std::cout<<"Equilibrium indices are: \n";
// traversing array from the end
for(int i=size-1;i>=0;i--){
if(right==(total_sum-arr[i]-right)){
std::cout<<i<<" ";
}
right+=arr[i];
}
}
int main(){
int arr[]={0,-3,5,-4,-2,3,1,0};
int size=sizeof(arr)/sizeof(arr[0]);
// function call to equilibriumIndex()
equilibriumIndex(arr,size);
}
Output:
Equilibrium indices are: 7 3 0
In Java
// Program to find equilibrium index of an array
// in linear time
// used for finding sum of elements of the array
import java.util.stream.IntStream;
public class equilibrium_index_optimized {
static void equilibriumIndex(int arr[]){
// sum of array arr elements
int total_sum=IntStream.of(arr).sum();
int size=arr.length;
// stores sum of right subarray arr[i+1...size-1]
int right=0;
System.out.println("Equilibrium Indices: ");
for(int i=size-1;i>=0;i--){
if(right==(total_sum-arr[i]-right)){
System.out.print(i+" ");
}
right+=arr[i];
}
}
public static void main(String[] args) {
int arr[]={0, -3, 5, -4, -2, 3, 1, 0};
equilibriumIndex(arr);
}
}
Output:
Equilibrium Indices: 7 3 0
In Python
# Program to find equilibrium index of an array
# in linear time
# function definition
def equilibriumIndex(arr):
# size of array
size=len(arr)
# sum of elements of array arr
total_sum=sum(arr)
# stores sum of subarray arr[i+1...size-1]
right=0
print("Equilibrium Indices: ")
for i in range(size-1,-1,-1):
if right==(total_sum-arr[i]-right):
print(i, end=" ")
right+=arr[i]
arr=[0, -3, 5, -4, -2, 3, 1, 0]
equilibriumIndex(arr)
Output:
Equilibrium Indices: 7 3 0
The time complexity of the above solution is O(n), where n is the input size of the array and doesn’t require any extra space.