Equilibrium Point

Equilibrium Point asks you to find the "balance" index of an array — a spot where the weight on the left exactly equals the weight on the right. It is a clean introduction to the prefix-sum mindset: avoid recomputing the same sums over and over by carrying a running total as you scan.

The slow way first

The obvious idea: for each index i, add up everything to its left, then add up everything to its right, and compare. But each of those sums is its own loop over the array, so for every one of n indices you do up to n work — that is O(n²). Most of it is wasted: the left sum at index i+1 is just the left sum at index i plus one more element.

The question to ask: as I move my candidate index one step to the right, what changes? Only one element moves from the right side to the left side. So I should be able to keep both sums up to date in O(1) per step instead of recomputing them.

The idea: carry a running left sum

First compute total, the sum of the whole array. Now sweep i from left to right while keeping leftSum = the sum of everything strictly before i. The right side then needs no separate loop at all:

rightSum = total - leftSum - a[i]

because the total is just left side + current element + right side. Whenever leftSum == rightSum, index i is the answer.

The key insight: the element at i belongs to neither side, which is why it gets subtracted out along with leftSum when we compute rightSum.

Walk through it

Step through the animation. The pointer i scans left to right. leftSum grows as cells turn into "visited" (the left side), and rightSum is read off the total each step. At i = 2, leftSum = 4 (from 1 + 3) and rightSum = 13 − 4 − 5 = 4 — they match, so index 2 is the equilibrium point.

Pseudocode

total   = sum of all elements
leftSum = 0
for each index i in a:
    rightSum = total - leftSum - a[i]   # everything after i, in O(1)
    if leftSum == rightSum:
        return i                         # found the balance point
    leftSum = leftSum + a[i]             # move a[i] onto the left side
return -1                                # no equilibrium index exists

The Python solution

def equilibrium_point(a):
    total = sum(a)
    left_sum = 0
    for i in range(len(a)):
        right_sum = total - left_sum - a[i]
        if left_sum == right_sum:
            return i
        left_sum += a[i]
    return -1

• total = sum(a) is one upfront pass so we never have to sum the right side again.
• left_sum holds the sum of everything strictly before the current index — it starts at 0.
• Line 5 is the trick: right_sum = total - left_sum - a[i] derives the right side in O(1) by subtracting the left side and the current element from the total.
• Line 6 compares the two sides; the first match is an equilibrium index.
• left_sum += a[i] happens after the check, moving the current element onto the left side for the next iteration.

Complexity

We compute the total in one pass and then sweep once more, doing O(1) work per index. No extra arrays are needed, so this runs in O(1) extra space — strictly better than the brute force on both time and memory.

When this pattern shows up

Practice