Find Pivot Index
Find Pivot Index: return the leftmost index where the sum of everything to its left equals the sum of everything to its right, or -1 if no such index exists.
- 1 <= nums.length <= 10⁴
- -1000 <= nums[i] <= 1000
Intuition
You never need to sum the right side — it is whatever the total is, minus the left sum, minus the pivot itself. Compute the total once, then sweep left to right carrying the left sum and testing that identity at each index.
Whenever both a prefix and a suffix of the same array are needed, compute the total once and derive the suffix by subtraction. That single trick collapses many two-pass or nested-loop problems into one sweep — it also solves Running Sum, Product of Array Except Self, and split-point questions generally.
Approach
Before reading on: if you know the total of the array and the sum of everything to the left of index i, can you get the right sum without another loop? Aim for O(n) and O(1) space.
Express the right side in terms of what you already have
For index i, the right sum is total - left - nums[i], where total is the sum of the whole array and left is the sum of everything strictly before i. That turns a two-sided question into a one-sided sweep: as long as you carry left, the right side is free. Without this identity you would recompute a suffix sum at every index, which is O(n²).
The sweep
Compute total in one pass. Set left = 0 and walk i from 0. At each index, check whether left == total - left - nums[i]; if so, return i immediately — the problem asks for the leftmost pivot and indices are tested in order. Otherwise add nums[i] to left and continue. The order matters: test before adding, because left must exclude the pivot itself.
Empty sides count as zero
At index 0 the left side is empty, and its sum is 0 — not undefined. So [−1,−1,−1,0,1,1] has a pivot at 0 when the rest happens to cancel, and [2,1,-1] pivots at index 0 because the left sum 0 equals the right sum 1 + (-1). The same applies at the last index, where the right side is empty. Treating empty as 0 rather than special-casing the ends is what keeps the loop uniform.
Solution & live demo
Common pitfalls
Adding to the left sum before testing
left += num if left == total - left - num:
if left == total - left - num:
return i
left += numThe left sum must exclude the pivot element itself. Adding first means left already contains nums[i], so the comparison is off by that value at every index.
Forgetting to subtract the pivot
if left == total - left:
if left == total - left - num:
The pivot belongs to neither side. Leaving it in the right-hand expression counts it as part of the right sum and reports pivots that do not exist.
Recomputing the right sum each iteration
if sum(nums[:i]) == sum(nums[i+1:]):
if left == total - left - num:
Both slices are O(n), making the loop O(n²) — and on 10⁴ elements that is 10⁸ operations. The running left plus the total already encodes everything needed.
Edge cases
Left sum is 0 and right sum is 0, so index 0 is returned.
The right side is empty and sums to 0; the test still works without a special case.
The loop finishes with no match and returns -1.
Both sides are empty and equal 0, so index 0 is the pivot.
The identity uses plain arithmetic, so signs need no special handling.