Find Pivot Index
Locate the index where the sum to its left equals the sum to its right, using a running sum and the total
Problem Statement
Given an array nums, find the leftmost pivot index — the index where the sum of all numbers strictly to its left equals the sum of all numbers strictly to its right.
The pivot element itself belongs to neither side. If no such index exists, return -1.
Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Why: left = 1 + 7 + 3 = 11
right = 5 + 6 = 11
Input: nums = [1, 2, 3]
Output: -1
Input: nums = [2, 1, -1]
Output: 0
Why: left = nothing = 0
right = 1 + (-1) = 0Intuition
The direct approach is: for each index, sum everything on the left, sum everything on the right, compare. Two inner loops per index makes it O(n²).
The key insight
You do not need to compute the right side at all. If you know the total of the whole array and the running left sum, then:
right = total - left - nums[i]
Both total and left are things you can maintain for free, so every index is checked in constant time.
Real-world analogy
Picture the array as weights on a seesaw and the pivot as the fulcrum. Rather than weighing both sides separately, weigh everything once. Then, as you slide the fulcrum right, whatever leaves the right side lands on the left side — the total never changes, so one measurement plus a running tally tells you both sides.
Approach
Compute the total sum once
That single O(n) pass replaces every future right-hand scan.
Walk left to right with left = 0
left holds the sum of everything before the current index.
Test each index
right = total - left - nums[i]. If left == right, return i — the first match is the leftmost pivot, which is what the problem asks for.
Then move the current element into left
left += nums[i] prepares the invariant for index i + 1. Adding after the test is essential, because the pivot element counts for neither side.
Return -1 if the loop finishes
No index balanced the two sides.
Watch it run
Solution
def pivot_index(nums: list[int]) -> int:
"""Return the leftmost index where the left and right sums match, else -1."""
total = sum(nums)
left = 0
for i, num in enumerate(nums):
right = total - left - num
if left == right:
return i
left += num # only after testing — the pivot belongs to neither side
return -1An equivalent formulation you will see
left == total - left - nums[i] rearranges to 2 * left + nums[i] == total. Some solutions test that form directly. It is the same condition with one fewer subtraction — use whichever reads more clearly to you.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — one pass to total the array plus one pass to scan it:
2n, which isO(n). - Space — two integers, regardless of input size.
Edge Cases
Related Problems
- Running Sum of 1d Array — the prefix-sum building block this problem consumes
- Product of Array Except Self — the same "everything except me" idea, with products
- Maximum Average Subarray I — maintaining a running sum without rescanning