Finding Equilibrium Index of an Array in Java

Understanding Equilibrium Index

The equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

We will explore three different methods to solve this problem in Java.

Method 1: Using Brute Force

public class EquilibriumIndex {
    public static void findEquilibrium(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int leftSum = 0, rightSum = 0;
            for (int j = 0; j < i; j++) leftSum += arr[j];
            for (int j = i + 1; j < n; j++) rightSum += arr[j];
            if (leftSum == rightSum) {
                System.out.println("Equilibrium Index: " + i);
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};
        findEquilibrium(arr);
    }
}
            

Output:

Equilibrium Index: 3
Equilibrium Index: 6
            

Method 2: Using Prefix Sum

public class EquilibriumIndex {
    public static void findEquilibrium(int[] arr) {
        int totalSum = 0, leftSum = 0;
        for (int num : arr) totalSum += num;
        for (int i = 0; i < arr.length; i++) {
            totalSum -= arr[i];
            if (leftSum == totalSum) {
                System.out.println("Equilibrium Index: " + i);
            }
            leftSum += arr[i];
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};
        findEquilibrium(arr);
    }
}
            

Output:

Equilibrium Index: 3
Equilibrium Index: 6
            

Method 3: Using Recursion

public class EquilibriumIndex {
    public static int equilibriumHelper(int[] arr, int index, int leftSum, int totalSum) {
        if (index == arr.length) return -1;
        totalSum -= arr[index];
        if (leftSum == totalSum) return index;
        return equilibriumHelper(arr, index + 1, leftSum + arr[index], totalSum);
    }
    
    public static void findEquilibrium(int[] arr) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;
        int eqIndex = equilibriumHelper(arr, 0, 0, totalSum);
        if (eqIndex != -1) System.out.println("Equilibrium Index: " + eqIndex);
    }
    
    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};
        findEquilibrium(arr);
    }
}
            

Output:

Equilibrium Index: 3