Find Pivot Index

Given an array of integers nums, return the pivot index: the index where the sum of the numbers strictly to its left equals the sum of the numbers strictly to its right. At the left edge the left sum is 0, and the same at the right edge. Return the leftmost pivot index, or -1 if none exists. This is LeetCode 724.

Example 1
Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: left sum 1 + 7 + 3 = 11, right sum 5 + 6 = 11.
Example 2
Input: nums = [1, 2, 3]
Output: -1
Example 3
Input: nums = [2, 1, -1]
Output: 0
Explanation: left sum 0 (nothing to the left), right sum 1 + (-1) = 0.

How to Think About It

Step 1: The simple way

For each index, add up both sides from scratch: O(n²).

Step 2: The right sum follows from the left sum

Compute the total once. At index i, everything is either left of i, at i, or right of i, so:

right = total - left - nums[i]

Step 3: Keep the left sum running

Walk from the left. Before moving past index i, compare left with right; then add nums[i] to left. The first match is the leftmost pivot.

Walkthrough

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

inums[i]leftright = 28 - left - nums[i]Equal?
01027no
17120no
23817no
361111yes: return 3

Java Solution

The left sum is updated after the comparison, so it never includes nums[i] itself.

Java
public class FindPivotIndex {

    public static int pivotIndex(int[] nums) {
        int total = 0;
        for (int x : nums) {
            total += x;
        }
        int left = 0;                         // sum of nums[0..i-1]
        for (int i = 0; i < nums.length; i++) {
            int right = total - left - nums[i];   // sum of nums[i+1..n-1]
            if (left == right) {
                return i;
            }
            left += nums[i];
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(pivotIndex(new int[] {1, 7, 3, 6, 5, 6}));   // 3
        System.out.println(pivotIndex(new int[] {1, 2, 3}));            // -1
        System.out.println(pivotIndex(new int[] {2, 1, -1}));           // 0
    }
}

The original implementation, FindPivotIndex.java, is on GitHub.

Complexity

  • Time: O(n): one pass for the total and one for the search.
  • Space: O(1).

Running sums like this are prefix sums; Range Sum Query - Immutable stores them to answer many queries.