Find Pivot Index

easy array prefix sum

Problem

Given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right. If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left.

Inputnums = [2, 4, 1, 7, 3, 5]

Output3

Left of index 3: 2 + 4 + 1 = 7. Right of index 3: 3 + 5 = 8. They are not equal at index 3 — but at no index do they match in this example, so the actual return is -1. (Try [1, 7, 3, 6, 5, 6] for a true pivot at index 3.)

nums (comma-separated)

def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        right = total - left - x
        if left == right:
            return i
        left += x
    return -1

function pivotIndex(nums) {
  let total = 0;
  for (const x of nums) total += x;
  let left = 0;
  for (let i = 0; i < nums.length; i++) {
    const right = total - left - nums[i];
    if (left === right) return i;
    left += nums[i];
  }
  return -1;
}

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

int pivotIndex(vector<int>& nums) {
    int total = 0;
    for (int x : nums) total += x;
    int left = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        int right = total - left - nums[i];
        if (left == right) return i;
        left += nums[i];
    }
    return -1;
}

Explanation

The pivot is the index where the sum to its left equals the sum to its right. The clean way to check this is to use the total sum so we never have to re-add the right side from scratch.

First compute total = sum(nums). Then sweep with a running left sum. At index i, the right sum is simply right = total - left - nums[i], because everything is the left part, the current element, and the right part.

If left == right, we found the pivot and return i. Otherwise we fold the current element into left and continue. If no index matches, we return -1.

Example: nums = [1,7,3,6,5,6]. At index 3, the left side 1+7+3 = 11 and the right side 5+6 = 11 match, so the answer is 3.

One pass to get the total and one pass to sweep makes this a fast O(n) solution using only a couple of variables.

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