Find Pivot Index
Problem statement
You're given an array of integers nums. The pivot index is a position where
the sum of everything strictly to its left equals the sum of everything
strictly to its right. If the position sits at either edge of the array, the
missing side counts as a sum of 0.
Return the leftmost pivot index. If no such index exists, return -1.
Examples
Example 1
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation: At index 3, the left side is 1 + 7 + 3 = 11 and the right
Example 2
Input: nums = [1,2,3]
Output: -1
Explanation: No index makes the left and right sums equal, so there is no
Example 3
Input: nums = [2,1,-1]
Output: 0
Explanation: At index 0, the left side has nothing to add, so it's 0.
Hints
Approach
Optimal: Total sum minus a running left sum
Intuition
The left sum, the value at the current index, and the right sum always add up
to the array's total — that never changes no matter where you are. So once
you know the total up front, you can get the right sum for free at every
index with a single subtraction: rightSum = total - leftSum - nums[i].
That removes the need to ever scan the right side directly, which is what
turns O(n²) into O(n).
Steps
- Compute
total, the sum of the whole array. - Start with
leftSum = 0. - For each index
ifrom0ton - 1:- Compute
rightSum = total - leftSum - nums[i]. - If
leftSum == rightSum, returni. - Otherwise, add
nums[i]toleftSumand move to the next index.
- Compute
- If the loop finishes with no match, return
-1.
Dry run
nums = [1, 7, 3, 6, 5, 6], total = 1+7+3+6+5+6 = 28
| i | nums[i] |
leftSum before |
rightSum = total − leftSum − nums[i] |
equal? | leftSum after |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 28 − 0 − 1 = 27 | no | 1 |
| 1 | 7 | 1 | 28 − 1 − 7 = 20 | no | 8 |
| 2 | 3 | 8 | 28 − 8 − 3 = 17 | no | 11 |
| 3 | 6 | 11 | 28 − 11 − 6 = 11 | yes → return 3 | — |
Every rightSum here is computed with one subtraction, using the running
leftSum — the right side of the array is never scanned directly.
Edge cases: for nums = [1, 2, 3] (Example 2), no index ever makes leftSum
equal rightSum, so the loop finishes and the function correctly returns
-1. For nums = [2, 1, -1] (Example 3), leftSum starts at 0 and
rightSum at index 0 is 2 - 0 - 2 = 0 — they already match, so the answer
is 0 even though the array contains a negative number; the subtraction
logic doesn't care about sign.
Complexity
Time O(n) - one pass to add up the total, then one more pass where each step does a constant amount of work: no more re-scanning the right side at every index.
Space O(1) - extra — just the total and a running left sum.
class Solution:
def pivotIndex(self, nums: list[int]) -> int:
total = sum(nums)
left_sum = 0
for i, x in enumerate(nums):
right_sum = total - left_sum - x
if left_sum == right_sum:
return i
left_sum += x
return -1
if __name__ == "__main__":
print(Solution().pivotIndex([1, 7, 3, 6, 5, 6])) # 3
print(Solution().pivotIndex([1, 2, 3])) # -1
print(Solution().pivotIndex([2, 1, -1])) # 0RecapThe whole problem in a few lines, for the night before
- Spot it: an index where the sum on the left equals the sum on the right
- Idea: compute the total once; walk the array and check left sum == total - left sum - nums[i]
- Cost: O(n) time, O(1) space
- Trap: the element at the pivot belongs to neither side, and an empty side counts as 0
Interview follow-ups
Return every pivot index, not just the leftmost.
Don't return as soon as one match is found — append the index to a results list instead, and keep going through the same single pass. The time complexity stays O(n); only the amount of output can grow.
numsarrives as a stream and can only be read once. How would this change?The trick needs the whole array's total before it can check even the first index, so a true single read isn't quite enough on its own. If a second pass over the same data is allowed, do this in two sweeps instead of one: one pass to compute
total, and a second pass to find the pivot exactly as before — still O(n) total, just split across two reads.numscan change over time, and you need the pivot index to stay current. What changes?Recomputing everything from scratch after every update costs O(n) each time. A Fenwick tree (binary indexed tree) supports both "update one value" and "sum of a prefix" in O(log n) each, so you can still use the same total-minus-
leftSumtrick, just backed by a structure that keeps prefix sums cheap to maintain asnumschanges.
Frequently asked questions
Because leftSum + nums[i] + rightSum always equals the array's total —
those three pieces split the whole array with nothing left over and nothing
double-counted. Once you know any two of the three, the last one is free:
just subtract. That's why the right side never needs to be scanned on its
own.
Because the loop checks indices in increasing order and returns the moment it finds a match. The very first index that satisfies the condition is necessarily the leftmost one, so there's no need to check the rest of the array once a match is found.
Picture nums as per-minute request counts across a window of time. A pivot
index is the minute that splits the earlier traffic and the later traffic
into two equal totals — a natural way to find a balance point, similar to
splitting a batch job's workload as evenly as possible across two halves.
No — sums and equality checks don't care whether the numbers are positive or
negative. Example 3, [2, 1, -1], shows this directly: the pivot at index 0
works out because 1 + (-1) happens to equal 0, exactly like an empty side
would.
