Back to solutions

Find Pivot Index

EasyArrays

Find the leftmost index where left-side sum equals right-side sum.

Open problem
Constraints
  • 1 <= n <= 10^4
  • -1000 <= nums[i] <= 1000

Prefix sum vs remaining

Time O(n)Space O(1)

Compute the full total once. Sweep left to right tracking the running sum to the left of i. The right side equals total - left - nums[i]. The first index where left equals that right value is the pivot.

Key terms
prefix sum:
The running total of all elements before the current index.
total:
The sum of every element, used to derive the right side cheaply.
int pivotIndex(vector<int>& nums) {
    long long total = 0;
    for (int x : nums) total += x;
    long long left = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (left == total - left - nums[i]) return i;
        left += nums[i];
    }
    return -1;
}
Step by step
  1. Add up all elements into total.
  2. Keep left = 0; for each i compute right = total - left - nums[i].
  3. If left == right, i is the answer (leftmost because we scan forward).
  4. Otherwise add nums[i] to left and continue; return -1 if nothing matched.