Find Pivot Index (LeetCode 724)

The problem

Given an integer array nums, find the pivot index: the leftmost index where the sum of everything strictly to its left equals the sum of everything strictly to its right. The element at the pivot itself is in neither sum. If no such index exists, return -1.

Input:  nums = [1, 7, 3, 6, 5, 6]
Output: 3

At index 3 (value 6), the left side is 1 + 7 + 3 = 11 and the right side is 5 + 6 = 11.

How to think about it

Start with brute force. For every index, add up the left part and the right part separately and compare. Each check is O(n), so the whole thing is O(n²). It works, but you are recomputing almost the same sums at every step.

The key insight: you only need one running sum. Walking left to right, keep left = the sum of everything before i. You know the total of the whole array up front, so the right side is simply total - left - nums[i]. No second loop, no extra array.

Why it is still a prefix-sum problem. left is just pre[i], and the right side is pre[n] - pre[i+1]. You never need the whole prefix array because you only ever look at the current position, so a single variable replaces it.

Which pattern is this? Prefix sums. The tell is “compare the sum on the left with the sum on the right” (often called an equilibrium index).

Approach

1. Compute total = sum(nums) and set left = 0.
2. Walk the array with index i and value x.
3. If left == total - left - x, return i. Checking before adding x is what keeps the pivot out of both sides.
4. Otherwise add x to left and continue.
5. If the loop ends, return -1.

Solution

def pivot_index(nums):
    total = sum(nums); left = 0
    for i, x in enumerate(nums):
        if left == total - left - x:   # right sum = total - left - x
            return i
        left += x                      # x joins the left side for the next index
    return -1
# pivot_index([1,7,3,6,5,6]) -> 3

Dry run

nums = [1, 7, 3, 6, 5, 6], total = 28.

Complexity

• Time: O(n). One pass for sum, one pass for the scan.
• Space: O(1). Only total and left are stored.

Edge cases and pitfalls

• Index 0 can be the pivot. The left sum is 0 there, so [2, 1, -1] returns 0 (right side is 1 + -1 = 0).
• The last index can be the pivot when everything before it sums to 0; the right side is empty, so it is 0.
• Return the leftmost pivot. Returning as soon as you find a match handles this; do not keep scanning and overwrite.
• Adding x too early puts the pivot into the left sum. Compare first, then add.
• Negative numbers are allowed, so you cannot stop early when left “gets too big”.

Related problems

• Range Sum Query - Immutable (LeetCode 303): the full prefix array that left is shorthand for.
• Product of Array Except Self (LeetCode 238): the same left-side / right-side split, with products.
• Minimum Value to Get Positive Step by Step Sum (LeetCode 1413): another one-variable running-sum scan.