Find The Equilibrium Index Of An Array In Java Program

An equilibrium index in an array is an index such that the sum of elements at lower indices is equal to the sum of elements at higher indices. If no such index exists, the function should indicate that. In this article, you will learn how to efficiently find an equilibrium index in a Java array.

Problem Statement

Identifying an equilibrium index in an array is a common algorithmic challenge. Given an array A of n integers, an index i is considered an equilibrium index if the sum of all elements A[0...i-1] is equal to the sum of all elements A[i+1...n-1]. Edge cases include: if i=0, the left sum is 0; if i=n-1, the right sum is 0. This problem is relevant in scenarios requiring balanced partitioning of data or resources.

Example

Consider the array: arr = {-7, 1, 5, 2, -4, 3, 0}

• At index 0 (value -7): Left sum = 0. Right sum = 1 + 5 + 2 - 4 + 3 + 0 = 7. Not equilibrium.
• At index 1 (value 1): Left sum = -7. Right sum = 5 + 2 - 4 + 3 + 0 = 6. Not equilibrium.
• At index 3 (value 2): Left sum = -7 + 1 + 5 = -1. Right sum = -4 + 3 + 0 = -1. This is an equilibrium index!
• At index 6 (value 0): Left sum = -7 + 1 + 5 + 2 - 4 + 3 = 0. Right sum = 0. This is also an equilibrium index!

The problem asks to find *an* equilibrium index, so any valid index is acceptable.

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, readers should have a basic understanding of:

• Java Fundamentals: Variables, data types, control flow (loops like for), and basic array manipulation.
• Arrays: How arrays are declared, initialized, and accessed in Java.
• Summation: Basic arithmetic operations for summing numbers.

No specific imports are required beyond standard Java libraries, which are typically handled implicitly or with import java.util.Scanner; for user input, though not strictly needed for the core problem.

Use Cases or Case Studies

The concept of an equilibrium index, or finding a "balancing point," appears in various computational contexts:

• Load Balancing: In distributed systems, finding an equilibrium point might help in distributing tasks evenly across servers, ensuring no single server is overloaded.
• Data Partitioning: When dividing a large dataset into two parts, an equilibrium index could represent a split point where the "weight" or "value" of data on both sides is balanced.
• Resource Allocation: In resource management, finding a point where resources allocated on one side balance those on the other can optimize usage.
• Financial Analysis: Identifying a point in a series of financial transactions where the cumulative gains/losses before and after that point are equal.
• Game Development: Balancing game mechanics or player statistics across different stages or scenarios.

Solution Approaches

Several methods can be employed to find an equilibrium index, varying in efficiency and complexity.

Approach 1: Brute-Force Method

This straightforward approach iterates through each possible index i in the array. For each i, it calculates the sum of elements to its left and the sum of elements to its right independently. If these two sums are equal, i is an equilibrium index.

• One-line summary: Iterate all possible indices and, for each, calculate left and right sums using nested loops.

// Brute-Force Equilibrium Index
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};
        int n = arr.length;

        System.out.println("Array: " + java.util.Arrays.toString(arr));
        int equilibriumIndex = findEquilibriumBruteForce(arr, n);

        if (equilibriumIndex != -1) {
            System.out.println("Equilibrium index (Brute Force): " + equilibriumIndex);
        } else {
            System.out.println("No equilibrium index found (Brute Force).");
        }
    }

    // Function to find equilibrium index using brute-force approach
    public static int findEquilibriumBruteForce(int[] arr, int n) {
        // Step 1: Iterate through each possible index i
        for (int i = 0; i < n; i++) {
            int leftSum = 0;
            int rightSum = 0;

            // Step 2: Calculate left sum for current index i
            for (int j = 0; j < i; j++) {
                leftSum += arr[j];
            }

            // Step 3: Calculate right sum for current index i
            for (int j = i + 1; j < n; j++) {
                rightSum += arr[j];
            }

            // Step 4: Compare left and right sums
            if (leftSum == rightSum) {
                return i; // Return the first equilibrium index found
            }
        }
        return -1; // No equilibrium index found
    }
}

Run

• Sample Output:

Array: [-7, 1, 5, 2, -4, 3, 0]
Equilibrium index (Brute Force): 3

• Stepwise explanation for clarity:

1. Initialize equilibriumIndex to -1.
2. Use an outer loop that iterates from i = 0 to n-1 (the length of the array). This i is our potential equilibrium index.
3. Inside this loop, initialize leftSum and rightSum to 0.
4. Use an inner loop to calculate leftSum: iterate j from 0 to i-1, adding arr[j] to leftSum.
5. Use another inner loop to calculate rightSum: iterate j from i+1 to n-1, adding arr[j] to rightSum.
6. After calculating both sums, compare leftSum and rightSum. If they are equal, i is an equilibrium index, so return i.
7. If the outer loop completes without finding an equilibrium index, return -1.
8. This approach has a time complexity of O(n^2) due to nested loops.

Approach 2: Using Prefix Sums

This method precomputes prefix sums for the array, allowing for O(1) calculation of sum of any subarray. While it still requires iterating to find the equilibrium index, it avoids recalculating sums from scratch in inner loops.

• One-line summary: Precompute cumulative sums into a prefix sum array, then iterate and check for equilibrium using these precalculated sums.

// Prefix Sums Equilibrium Index
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};
        int n = arr.length;

        System.out.println("Array: " + java.util.Arrays.toString(arr));
        int equilibriumIndex = findEquilibriumPrefixSums(arr, n);

        if (equilibriumIndex != -1) {
            System.out.println("Equilibrium index (Prefix Sums): " + equilibriumIndex);
        } else {
            System.out.println("No equilibrium index found (Prefix Sums).");
        }
    }

    // Function to find equilibrium index using prefix sums
    public static int findEquilibriumPrefixSums(int[] arr, int n) {
        if (n == 0) return -1;

        // Step 1: Create a prefix sum array
        int[] prefixSum = new int[n];
        prefixSum[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        // Step 2: Iterate through each index i to find equilibrium
        for (int i = 0; i < n; i++) {
            // Step 3: Calculate left sum
            // If i is 0, left sum is 0. Otherwise, it's prefixSum[i-1].
            int leftSum = (i == 0) ? 0 : prefixSum[i - 1];

            // Step 4: Calculate right sum
            // If i is n-1, right sum is 0. Otherwise, it's total sum - prefixSum[i].
            int rightSum = (i == n - 1) ? 0 : (prefixSum[n - 1] - prefixSum[i]);

            // Step 5: Compare left and right sums
            if (leftSum == rightSum) {
                return i; // Return the first equilibrium index found
            }
        }
        return -1; // No equilibrium index found
    }
}

Run

• Sample Output:

Array: [-7, 1, 5, 2, -4, 3, 0]
Equilibrium index (Prefix Sums): 3

• Stepwise explanation for clarity:

1. Handle the empty array case: if n is 0, return -1.
2. Create a prefixSum array of the same size as arr.
3. Populate prefixSum: prefixSum[0] is arr[0]. For i > 0, prefixSum[i] is prefixSum[i-1] + arr[i]. This takes O(n) time.
4. Initialize equilibriumIndex to -1.
5. Iterate i from 0 to n-1.
6. Calculate leftSum: If i is 0, leftSum is 0. Otherwise, leftSum is prefixSum[i-1].
7. Calculate rightSum: If i is n-1, rightSum is 0. Otherwise, rightSum is prefixSum[n-1] - prefixSum[i]. prefixSum[n-1] represents the total sum of the array.
8. If leftSum equals rightSum, then i is an equilibrium index. Return i.
9. If the loop finishes without finding an index, return -1.
10. This approach has a time complexity of O(n) for precomputation and O(n) for finding the index, totaling O(n). It uses O(n) auxiliary space for the prefixSum array.

Approach 3: Optimized Single-Pass Method

This is the most efficient approach, requiring only a single pass after calculating the total sum of the array. It maintains a leftSum that grows as we iterate, and derives rightSum from the totalSum, leftSum, and the current element.

• One-line summary: Calculate total array sum, then iterate once, updating leftSum and deriving rightSum to find equilibrium.

// Single-Pass Equilibrium Index
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};
        int n = arr.length;

        System.out.println("Array: " + java.util.Arrays.toString(arr));
        int equilibriumIndex = findEquilibriumOptimized(arr, n);

        if (equilibriumIndex != -1) {
            System.out.println("Equilibrium index (Optimized Single Pass): " + equilibriumIndex);
        } else {
            System.out.println("No equilibrium index found (Optimized Single Pass).");
        }
    }

    // Function to find equilibrium index using optimized single pass
    public static int findEquilibriumOptimized(int[] arr, int n) {
        // Step 1: Calculate the total sum of the array
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            totalSum += arr[i];
        }

        int leftSum = 0; // Initialize left sum to 0

        // Step 2: Iterate through the array to find the equilibrium index
        for (int i = 0; i < n; i++) {
            // Step 3: Calculate the right sum for the current index i
            // rightSum = totalSum - leftSum - arr[i]
            // (totalSum - leftSum) is the sum of elements from current index i to the end.
            // Subtracting arr[i] gives the sum of elements after index i.
            int rightSum = totalSum - leftSum - arr[i];

            // Step 4: Compare leftSum and rightSum
            if (leftSum == rightSum) {
                return i; // Return the first equilibrium index found
            }

            // Step 5: Update leftSum for the next iteration
            leftSum += arr[i];
        }
        return -1; // No equilibrium index found
    }
}

Run

• Sample Output:

Array: [-7, 1, 5, 2, -4, 3, 0]
Equilibrium index (Optimized Single Pass): 3

• Stepwise explanation for clarity:

1. First, calculate totalSum of all elements in the array. This takes O(n) time.
2. Initialize leftSum to 0. This variable will store the sum of elements to the left of the current index i.
3. Iterate i from 0 to n-1.
4. Inside the loop, calculate rightSum. The rightSum for the current i is totalSum - leftSum - arr[i]. This formula works because totalSum - leftSum gives the sum of elements from the current arr[i] to the end of the array. Subtracting arr[i] then gives the sum of elements *after* arr[i].
5. Compare leftSum and rightSum. If they are equal, i is an equilibrium index. Return i.
6. Before moving to the next iteration, update leftSum by adding arr[i] to it. This prepares leftSum for the next index i+1.
7. If the loop completes without finding an equilibrium index, return -1.
8. This approach has a time complexity of O(n) (one pass for totalSum, one pass for finding the index) and an auxiliary space complexity of O(1).

Conclusion

Finding an equilibrium index is a classic problem with various real-world applications. While a brute-force approach provides a simple solution, its O(n^2) time complexity makes it inefficient for large arrays. The prefix sum method improves efficiency to O(n) time but uses O(n) additional space. The most optimized solution, a single-pass approach, achieves O(n) time complexity with only O(1) auxiliary space, making it the preferred method for practical implementations.

Summary

• An equilibrium index i means the sum of elements before i equals the sum of elements after i.
• Brute-Force: Iterates through each index, calculates left and right sums in nested loops. Time complexity: O(n^2). Space complexity: O(1).
• Prefix Sums: Precomputes cumulative sums, then uses them to find left/right sums in O(1). Time complexity: O(n). Space complexity: O(n).
• Optimized Single-Pass: Calculates total sum once, then iterates, maintaining leftSum and deriving rightSum. Time complexity: O(n). Space complexity: O(1).
• The optimized single-pass method is generally the most efficient due to its linear time complexity and constant auxiliary space.