Find Pivot Index

How it works

We can eliminate the need for a separate prefix sum array by maintaining a running left sum and computing the right sum on the fly. First, calculate the total sum of the array. As we iterate, the right sum at any index equals total - leftSum - nums[i]. We update leftSum after each comparison, keeping space usage constant.

Steps

1. Compute the total sum of the array.
2. Initialize leftSum = 0.
3. For each index i:
   • Compute rightSum = total - leftSum - nums[i].
   • If leftSum == rightSum, return i.
   • Add nums[i] to leftSum.
4. If no pivot is found, return -1.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Confusing Empty Sum as Zero

When the pivot is at index 0, the left sum is 0 (sum of no elements). Similarly, when the pivot is at the last index, the right sum is 0. Some solutions incorrectly skip checking the first or last index, assuming a pivot must have elements on both sides. The problem defines sums of empty ranges as 0, so boundary indices are valid pivot candidates.

Including the Pivot Element in the Sum

The pivot index itself should not be included in either the left sum or the right sum. A common mistake is computing leftSum as the sum up to and including index i, or computing rightSum starting from index i. The correct formula is rightSum = total - leftSum - nums[i], which explicitly excludes the pivot element from both sums.

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        leftSum = 0
        for i in range(len(nums)):
            rightSum = total - nums[i] - leftSum
            if leftSum == rightSum:
                return i
            leftSum += nums[i]
        return -1

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }

        int leftSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            int rightSum = total - leftSum - nums[i];
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
};