Equilibrium Index of an Array in Java

In this section, we will learn what is equilibrium index in an array and how to find the equilibrium index through a Java program.

Equilibrium Index

If the sum of lower indices elements is equal to the sum of higher indices elements is called an equilibrium index of an array

For example, consider the array [-7, 1, 5, 2, -4, 3, 0], where:

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

Let’s find the equilibrium index. According to the definition:

The sum of elements at lower indices is = a[0]+a[1]+a[2] = -7+1+5 = -1

The sum of elements at higher indices is = a[4]+a[5]+a[6] = -4+3+0 = -1

We observe that the sum of elements at lower indices is equal to the sum of elements at higher indices. Hence, for the given array an equilibrium index is 3.

In the above array, 6 is also an equilibrium index because the sum of a[0] to a[5] is 0, and the value of index a[6] is 0.

Equilibrium Index of an Array in Java

Methods to find the Equilibrium Index

There are the three methods to find the equilibrium index of an array:

Brute Force Approach
Using an Iterative Approach
Using an Incremental Approach

Brute Force Approach

In this approach, we use two loops. The outer loop iterates over the array and the inner loop checks if there exists an equilibrium index or not. The idea is to find the sum of elements for every range of indexes and observe if exists an equilibrium index. It takes O(n²) time and space complexity O(1) to solve the problem.

Algorithm Steps

Iterate a loop over the array.
For each index, find the sum of elements towards the left and right of the current index.
If the lsum and rsum is equal, the current index is an equilibrium index.
Else, return -1.

Let’s implement the above logic in a Java program.

EquilibriumIndexExample1.java

  public class EquilibriumIndexExample1  {  //function to find the equilibrium index  static int eqbmindex(int array[], int n)  {  int i, j;  //lsum denotes the left sum and rsum denotes the right sum  int lsum, rsum;  for (i = 0; i < n; ++i)   {  lsum = 0;  //finds the sum upto current index (exclude)  for (j = 0; j < i; j++)  lsum = lsum + array[j];  rsum = 0;  //finds the sum from current index to last index (exclude)  for (j = i + 1; j < n; j++)  rsum = rsum + array[j];  //if rsum and lsum are equal, returns i (equilibrium index), else returns -1  if (lsum == rsum)  return i;  }  return -1;  }  public static void main(String args[])  {  int array[] = {9, 3, 7, 6, 8, 1, 10};  int arraysize = array.length;  System.out.print(“Equilibrium Index is: “);  System.out.println(eqbmindex(array, arraysize));  }  }  

Output:

Equilibrium Index is: 3

In the above approach, we have used nested loop for calculating the left and right sum for each value of i. It performs n(n-1) summation operations.

Using an Iterative Approach

The approach uses some extra space. In this approach, we store the prefix sum of the array. It keeps track the sum of all the elements up to any index of the array. Now, we need to track the sum of values to the right of the current index.

To find the sum of values to the right of current index, subtract the value at the current index. Now compare the lsum and rsum, if they are equal the current index is equilibrium index.

Algorithm Steps

Store prefix sum of the array by suing some extra space.
Find the total sum of the array and store it as right sum (rsum).
Traverse over the array and compare the rsum with lsum.
If rsum and lsum are equal, return i (current index).
Else, return -1.

It’s time and space complexity are O(n). Let’s implement the above algorithm in a Java program.

EquilibriumIndexExample2.java

  public class EquilibriumIndexExample2  {  static int eqbmindex(int array[], int n)  {  //lsum denotes the left sum and rsum denotes the right sum  int prefix[n];  //stores the sum of whole array  for (int i = 0; i < n; i++)  {  if(i==0)   prefix[i] = array[i];  else prefix[i] = array[i] + prefix[i-1];  }  int rsum = prefix[n-1];  for(int i = 0 ; i < n; i++)  {  rsum = rsum – array[i];  int lsum = prefix[i+1];  if(rsum = rsum)  return i + 1;  }  return -1;  }  public static void main(String args[])  {  int array[] = {0, -4, 7, -4, -2, 6, -3, 0};  int arraysize = array.length;  System.out.print(“Equilibrium Index is: “);  System.out.println(eqbmindex(array, arraysize));  }  }  

Output:

Equilibrium Index is: 5

Using an Incremental Approach

The incremental approach is the same as iterative approach except some things. The difference between the approach and the previous approach (iterative approach) is that we need not to store the prefix sum. Instead, we keep track of the left sum at the same time while iterating over the array. In this approach, first we calculate the total sum of the array. To get the right sum, inside the loop we subtract the element one by one. It’s time and space complexity is O(n) and O(1), respectively.

Algorithm Steps

Store the total sum of the array in the variable tsum.
Iterate over the array and keep track of the lsum by adding the value at the current index (i) and rsum by subtracting the value at the current index from tsum.
If lsum and rsum are equal, return the current index (i).
Else, return -1.

Let’s implement the above approach in a Java program.

EquilibriumIndexExample3.java

  public class EquilibriumIndexExample3  {  static int eqbmindex(int array[], int n)  {  //lsum denotes the left sum and rsum denotes the right sum  int rsum = 0;  int lsum = 0;  //stores the sum of whole array  for (int i = 0; i < n; ++i)  rsum = rsum + array[i];  for (int i = 0; i < n; ++i)   {  //updates rsum  rsum = rsum – array[i];  //if rsum and lsum are equal, returns i (equilibrium index), else returns -1  if (lsum == rsum)  return i;  lsum = lsum + array[i];  }  return -1;  }  public static void main(String args[])  {  int array[] = {2, 9, 3, 4, 0, 3, 3, 2, 9, 1};  int arraysize = array.length;  System.out.print(“Equilibrium Index is: “);  System.out.println(eqbmindex(array, arraysize));  }  }  

Output 1:

Equilibrium Index is: 4

Output 2:

Equilibrium Index is: -1

Next TopicDifferent Ways to Print Exception Message in Java

Equilibrium Index of an Array in Java

Equilibrium Index of an Array in Java

Equilibrium Index

Methods to find the Equilibrium Index

Brute Force Approach

Using an Iterative Approach

Using an Incremental Approach

Convert List to Array in Java

Java Garbage Collection

You may also like