Equilibrium Point in Java: Algorithm & Practice

Find index where left sum equals right sum

Problem summary

Find an index where sum of elements to the left equals sum of elements to the right.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 2, 2}; // Test case 1
        
        // Find equilibrium index
        // Print: Index: <i> OR No equilibrium
    }
}

Expected output and test cases

1+3 = 2+2 at index 2
```
Index: 2
```
Left sum 0 = right sum 0
```
Index: 0
```
No valid index
```
No equilibrium
```

Hints

Calculate total sum first
Iterate: leftSum, rightSum = total - leftSum - arr[i]
Check if equal at each index

Validated solution

Reveal Java solution

public class Main {
    static int equilibriumIndex(int[] values) {
        int right = 0;
        for (int value : values) right += value;
        int left = 0;
        for (int index = 0; index < values.length; index++) {
            right -= values[index];
            if (left == right) return index;
            left += values[index];
        }
        return -1;
    }
    public static void main(String[] args) {
        int index = equilibriumIndex(new int[] {1, 3, 5, 2, 2});
        System.out.println("Index: " + index);
    }
}

How to approach the problem

Compute the full sum once. At each index, remove the current value from the right total before comparing it with the accumulated left total, then add it to the left for the next iteration.

Approach

Calculate the total right-side sum.
Exclude the current value from the right side.
Compare, then grow the left-side sum.

Time and space complexity

Time: O(n). Space: O(1).

Constraints

The input must be a finite integer array.
An index at either end is valid when the elements on the opposite side sum to zero.

Edge cases to test

An endpoint can qualify because the sum on its outer side is zero.
Large totals may need long rather than int.

Common mistakes

Including the current value in either side.
Recomputing two sums for each index, which is quadratic.

Follow-up challenge

Return every equilibrium index instead of stopping at the first.

Related Arrays exercises

Practice all Arrays exercises · Run this idea in the Java compiler