Find the Equilibrium Index of an Array

An equilibrium index exists at position i when the sum of all elements to the left of i equals the sum of all elements to the right of i.

The element at index i itself is not included in either sum. If no such position exists, the function returns -1.

Two approaches solve this. The brute-force O(n²) method recomputes sums for every candidate index from scratch. The O(n) prefix-sum method computes the total once and derives each right-side sum in constant time. Placement tests frequently ask which approach is optimal and why. Both answers are below.

What Counts as an Equilibrium Index

Formally, index i is an equilibrium index of array arr with length n if:

arr[0] + arr[1] + ... + arr[i-1] equals arr[i+1] + arr[i+2] + ... + arr[n-1]

For i = 0, the left sum is 0 because there are no elements to the left. For i = n-1, the right sum is 0 for the same reason. Both boundaries are valid equilibrium positions when the opposite side sums to 0.

An array can have multiple equilibrium indices. In {0, 0, 0} every position qualifies. The standard problem returns the first one found; -1 signals that none exists.

Manual verification on the classic example, {-7, 1, 5, 2, -4, 3, 0}:

• Total sum: -7 + 1 + 5 + 2 + (-4) + 3 + 0 = 0
• Left of index 3: -7 + 1 + 5 = -1
• Right of index 3: -4 + 3 + 0 = -1
• Left sum == right sum, so index 3 is the equilibrium index.

Verifying the example before writing any code is a practice worth keeping. The WP source for this problem had the right answer; not all legacy problems do. Confirming by hand takes 60 seconds and prevents shipping code that passes wrong test cases.

For array traversal problems that follow a similar scan-and-compare pattern, see find smallest and largest element in an array.

Brute-Force O(n²) Approach

The direct solution runs a nested loop. For each candidate index i, two inner loops compute the left sum and right sum before comparing them.

Algorithm

• For each index i from 0 to n-1:
  • Compute leftSum as the sum of arr[0] through arr[i-1]
  • Compute rightSum as the sum of arr[i+1] through arr[n-1]
  • If leftSum == rightSum, return i
• If no match found, return -1

Trace on {-7, 1, 5, 2, -4, 3, 0}

Index	Left Sum	Right Sum	Match?
0	0	7	No
1	-7	6	No
2	-6	1	No
3	-1	-1	Yes — return 3

The loop exits at index 3. The approach is correct but repeats work: computing the left sum at index 3 starts again from index 0, reusing nothing from the previous step.

Complexity

• Time: O(n²) — two inner loops for each of n outer indices.
• Space: O(1) — two running sum variables, nothing proportional to input size.

The O(n) Prefix-Sum Method

The key insight: at any index i, the right sum equals total - leftSum - arr[i]. Since total is fixed after a single initial pass, each index needs only a constant-time computation.

Algorithm

• Compute total as the sum of all elements in the array
• Set leftSum = 0
• For each index i:
  • If leftSum == total - leftSum - arr[i], return i
  • Add arr[i] to leftSum
• Return -1

Trace on {-7, 1, 5, 2, -4, 3, 0} (total = 0)

Index	arr[i]	leftSum (before check)	total - leftSum - arr[i]	Match?
0	-7	0	7	No
1	1	-7	6	No
2	5	-6	1	No
3	2	-1	-1	Yes — return 3

At index 3: leftSum = -1, derived right sum = 0 - (-1) - 2 = -1. They match.

This is an application of the prefix-sum technique, a well-documented approach for turning repeated range-sum computations into single-pass operations. The GeeksforGeeks equilibrium index reference lists several array variants that build on the same idea.

Complexity

• Time: O(n) — one pass to compute total, one pass to find the equilibrium index.
• Space: O(1) — two integer variables regardless of input size.

Code in C, C++, Python, and Java

The four implementations below cover both approaches. The brute-force version is included to make the complexity difference concrete.

C

#include <stdio.h>

/* Brute force: O(n^2) time */
int equilibriumBrute(int arr[], int n) {
    int i, j, leftSum, rightSum;
    for (i = 0; i < n; i++) {
        leftSum = 0;
        rightSum = 0;
        for (j = 0; j < i; j++)
            leftSum += arr[j];
        for (j = i + 1; j < n; j++)
            rightSum += arr[j];
        if (leftSum == rightSum)
            return i;
    }
    return -1;
}

/* Prefix-sum: O(n) time */
int equilibriumOptimal(int arr[], int n) {
    int total = 0, leftSum = 0, i;
    for (i = 0; i < n; i++)
        total += arr[i];
    for (i = 0; i < n; i++) {
        if (leftSum == total - leftSum - arr[i])
            return i;
        leftSum += arr[i];
    }
    return -1;
}

int main() {
    int arr[] = {-7, 1, 5, 2, -4, 3, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Equilibrium index: %d\n", equilibriumOptimal(arr, n));
    return 0;
}

C++

The C++ version uses std::vector and std::accumulate for idiomatic style.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int equilibriumOptimal(const vector<int>& arr) {
    int total = accumulate(arr.begin(), arr.end(), 0);
    int leftSum = 0;
    for (int i = 0; i < (int)arr.size(); i++) {
        if (leftSum == total - leftSum - arr[i])
            return i;
        leftSum += arr[i];
    }
    return -1;
}

int main() {
    vector<int> arr = {-7, 1, 5, 2, -4, 3, 0};
    cout << "Equilibrium index: " << equilibriumOptimal(arr) << endl;
    return 0;
}

Python

def equilibrium_brute(arr):
    n = len(arr)
    for i in range(n):
        if sum(arr[:i]) == sum(arr[i+1:]):
            return i
    return -1

def equilibrium_optimal(arr):
    total = sum(arr)
    left_sum = 0
    for i, val in enumerate(arr):
        if left_sum == total - left_sum - val:
            return i
        left_sum += val
    return -1

arr = [-7, 1, 5, 2, -4, 3, 0]
print("Equilibrium index:", equilibrium_optimal(arr))  # Output: 3

Java

public class EquilibriumIndex {

    static int equilibriumBrute(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) return i;
        }
        return -1;
    }

    static int equilibriumOptimal(int[] arr) {
        int total = 0;
        for (int val : arr) total += val;
        int leftSum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (leftSum == total - leftSum - arr[i]) return i;
            leftSum += arr[i];
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};
        System.out.println("Equilibrium index: " + equilibriumOptimal(arr));
    }
}

All four output Equilibrium index: 3 for the example input. The FACE Prep data structures collection covers insertion, deletion, and linked-list operations across the same language set, which rounds out the standard array and pointer problems that appear alongside equilibrium-index questions in placement coding rounds.

Complexity Comparison

Approach	Time	Space	Repeated computation?
Brute force	O(n²)	O(1)	Yes — recomputes both sums from scratch each iteration
Prefix-sum	O(n)	O(1)	No — total computed once; right sum derived algebraically

Both approaches use O(1) space because neither allocates an auxiliary array. The prefix-sum method stores only two integer variables (total and leftSum) regardless of input size.

When a placement test asks for the optimal solution, the expected answer is O(n) time and O(1) space. If asked to justify the O(n) bound: one pass to sum the array, one pass to find the equilibrium index, with each loop visiting n elements exactly once.

A related pattern appears in the insert, delete, and search program, where maintaining a running state variable across a single traversal similarly avoids repeated linear scans.

Edge Cases to State in Interviews

• Empty array (n = 0): Both implementations return -1. Mention this explicitly.
• Single element (n = 1): Index 0 has an empty left side (sum = 0) and an empty right side (sum = 0). Both sides are equal, so index 0 is always the equilibrium index for a single-element array.
• All identical elements: If all elements are 0, every index is an equilibrium index. If all elements are non-zero and identical (e.g., {3, 3, 3}), the total is 9; at index 1, leftSum = 3 and total - leftSum - arr[1] = 9 - 3 - 3 = 3. Left equals right, so index 1 is the equilibrium index for {3, 3, 3}.
• Array sums to non-zero: Most arrays do not have an equilibrium index. The function returning -1 is the common case, not the edge case.

Covering these four scenarios when explaining a solution in a technical interview moves the answer from “correct implementation” to “complete analysis.”

---

The “compute once, reuse many times” pattern that makes the O(n) prefix-sum solution efficient here appears in the same form in ML data pipelines: rolling-window feature computation, cumulative-sum normalisation for time-series inputs, and attention-score caching all rely on the same principle. TinkerLLM is a hands-on environment where you can experiment with those LLM API patterns yourself, starting at ₹299 for a month of access.