Equilibrium Index of an Array in Java

An array's equilibrium index is the condition where the sum of items with lower and higher indices equals. For example, an array A=[-4,5 2,6,-5] where:

a[0]=-4, a[1]=5, a[2]=2, a[3]=6, a[4]=-5

Now according to the definition:

The sum of the elements at lower index positions are=a[0]+a[1]=-4+5=1

The sum of the elements at higher index positions are =a[2]+a[3]=6+-5=1

We observe that the sum of the elements at lower and higher index positions is equal. So, the equilibrium index value is 2.

Methods to calculate the equilibrium index

There are three ways to determine an array's equilibrium index:

1. Using a brute force approach

2. An incremental approach

3. An iterative approach

Brute force approach

In this method, we implement two loops. The inner loop determines whether or not an equilibrium index exists, while the outer loop iterates across the array. The objective is to compute the elemental total for each index range and determine whether an equilibrium index exists. The problem can be solved in O(n2) time with O(1) space.

Algorithm

• The array is iterated.

• Finding the left and right index values for the current index are found. Should find the total components to the left and right of the current index for each index.
• The current index is an equilibrium if the Lsum and the Rsum are equal.
• Otherwise, return 0.

Implementation

Filename: EquilibriumIndexEx1.java

//Java Program for finding equilibrium index
//importing packages
import java.io.*;
Import java.util.*;
public class EquilibriumIndexEx1  
{  
// function for finding the index value 
static int eqlindex(int arr[], int num)  
{  
int i, j;  
// Lsum denotes the sum of left elements, and Rsum denotes the sum of Right elements
int Lsum, Rsum;  
for (i = 0; i < num; ++i)   
{  
Lsum = 0;  
// the sum of values upto the current index  
for (j = 0; j < i; j++)  
Lsum = Lsum + arr[j];  
Rsum = 0;  
// finding the sum from the current value to the last index
for (j = i + 1; j < num; j++)  
Rsum = Rsum + arr[j];  
//if Rsum and Lsum are equal returns i (equilibrium index), else return -1  
if (Lsum == Rsum)  
return i;  
}  
return -1;  
}  
public static void main(String args[])  
{  
int arr[] = {9, 11, 7, 8, 8, 9, 10};  
int l = arr.length;  
System.out.print("The Equilibrium Index position is: ");  
System.out.println(eqlindex(arr,l));  
}  
}  

Output

The Equilibrium Index position is: 3

Applying an Iterative Process

This process made advantage of some excess space. With this method, we save the array's prefix sum. It maintains track of the total of all elements up to an array index. The sum of numbers to the right of the current index must now be checked.

Subtract the number at the current index to get the total numbers to the right. The current index is the equilibrium index when the Lsum and Rsum are equivalent.

Algorithm

• Allocate some additional space to store the array's prefixed sum.
• Identify the array's total sum and save it as the correct sum (Rsum).
• Check the Rsum and Lsum values by iterating over the array.
• i should be returned if Rsum and Lsum are equal (current index).
• Otherwise, return 0.

The time complexity for implementation is O(n).

Filename: EquilibriumIndexEx2.java

//Java Program for finding the equilibrium index
import java.io.*;
import java.util.*;
public class EquilibriumIndexEx2  
{  
static int eqlindex(int arr[], int num)  
{  
//Lsum and Rsum stand for left and right sums, respectively. 
int prefixs[]=new int[num];  
// the array of the sum
for (int i = 0; i < num; i++)  
{  
if(i==0)   
prefixs[i] = arr[i];  
else prefixs[i] = arr[i] + prefixs[i-1];  
}  
int Rsum = prefixs[num-1];  
for(int i = 0 ; i < num; i++)  
{  
Rsum = Rsum - arr[i];  
int Lsum = prefixs[i+1];  
if(Rsum==Lsum)  
return i + 1;  
}  
return -1;  
}  
public static void main(String args[])  
{  
int arr[] = {0, -3, 6, -5, -1, 6, -2, 0};  
int l = arr.length;  
System.out.print("The Equilibrium Index value is: ");  
System.out.println(eqlindex(arr,l));  
}  
}  

Output

The Equilibrium Index value is: 3

A Step-by-Step Approach

The incremental approach is similar to the iterative technique, with a few exceptions. It has O(n) time complexity and O(1) space complexity. The method differs from the prior(iterative method) in that we do not need to keep the prefix sum. Instead, while iterating through the array, we maintain track of the left sum. In this method, we start by computing the array's overall sum. To obtain the correct value.

Steps in an Algorithm

• Put the Tsum variable's value as the array's total.
• During each iteration of the array, add the value at the current index i to the Lsum and remove the value at the present index from the Rsum to maintain track of the Lsum.
• The current index returns if Lsum and Rsum are equal (i).
• Otherwise, return 0.

Filename: EquilibriumIndexEx3

//Java Program for finding the Equilibrium index
import java.io.*;
import java.util.*;
public class EquilibriumIndexEx3  
{  
static int eqbmindex(int arr[], int num)  
{  
//Lsum indicates the left indexes sum, and Rsum indicates the right indexes 
int Rsum = 0;  
int Lsum = 0;  
// The Total sum of the array
for (int i = 0; i < num; ++i)  
Rsum = Rsum + arr[i];  
for (int i = 0; i < num; ++i)   
{  
//The Rsum is updated
Rsum = Rsum - arr[i];  
//it checks the left and right array sum
if (Lsum == Rsum)  
return i;  
Lsum = Lsum + arr[i];  
}  
return -1;  
}  
public static void main(String args[])  
{  
int arr[] = {1, 3, 6, 4, 1, 0, 3, 2, 5, 4};  
int l = arr.length;  
System.out.print("The Equilibrium Index is: ");  
System.out.println(eqbmindex(arr,l));  
}  
}  

Output

The Equilibrium Index is: 4