Find Pivot Index

Find Pivot Index is a prefix-sum balance problem. At each index, the question is: "Is the sum on my left equal to the sum on my right?"

Problem

Given an integer array nums, return the leftmost pivot index.

A pivot index is an index where:

sum(nums[0..i-1]) == sum(nums[i+1..n-1])

The current element is not included in either side.

If no pivot index exists, return -1.

First Attempt

public int pivotIndex(int[] nums) {
    int n = nums.length;
    int sum = 0;
    for (int a : nums) sum += a;

    int lSum = 0;
    int rSum = sum;
    for (int i = 0; i < n; i++) {
        rSum -= nums[i];
        if (lSum == rSum) {
            return i;
        }
        lSum += nums[i];
    }
    return -1;
}

This is already the right approach. It computes the total sum once, then walks through the array while maintaining:

• lSum: sum of values strictly to the left of i
• rSum: sum of values strictly to the right of i

The important move is subtracting nums[i] from rSum before checking. That removes the current element from the right side.

Clean Version

class Solution {
    public int pivotIndex(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            int rightSum = total - leftSum - nums[i];

            if (leftSum == rightSum) {
                return i;
            }

            leftSum += nums[i];
        }

        return -1;
    }
}

This version avoids carrying a mutable rightSum. Both versions are O(n), but this one makes the balance formula explicit:

rightSum = total - leftSum - nums[i]

Walkthrough

Input:

nums = [1, 7, 3, 6, 5, 6]

Total:

1 + 7 + 3 + 6 + 5 + 6 = 28

Steps:

At index 3, the left side is:

1 + 7 + 3 = 11

The right side is:

5 + 6 = 11

So the pivot index is 3.

Edge Cases

[1, 7, 3, 6, 5, 6] -> 3
[1, 2, 3] -> -1
[2, 1, -1] -> 0

The third case returns 0 because the left sum is empty, so it is 0, and the right side is 1 + -1 = 0.

Complexity

Takeaways

• Compute the total sum first.
• At each index, exclude the current value from both sides.
• Use rightSum = total - leftSum - nums[i] to make the balance check clear.
• Return as soon as a match is found, because the problem asks for the leftmost pivot index.