724. Find Pivot Index
Easy · solved 2026-10-01 · Open on LeetCode
prefix-sumarray
Time O(n) · Space O(1)
How to get there
Move the split, don't re-add the sides
1. Check every index by hand. On [1, 7, 3, 6, 5, 6], index 3 has 1 + 7 + 3 = 11 on its left and 5 + 6 = 11 on its right. Adding both sides from scratch at every index works, but costs O(n) per index.
2. Compare neighbouring indices. Moving the split from index i − 1 to index i changes each side by one number: nums[i - 1] joins the left, and nums[i] leaves the right. Everything else stays where it was.
3. What to carry: both sums. Keep the left sum and the right sum, and update each by that one number per step. Before index 0, nothing is on the left and every number is on the right, so the left starts at 0 and the right at the total.
4. Why every index is checked, in order. The numbers can be negative, so neither sum grows steadily, and a balance at one index says nothing about the next. Scanning from the left makes the first balance found the leftmost pivot, which is the one asked for.
The reusable recipe: when a sum over a range changes by one element as the boundary moves, update it by that element instead of adding the range again.
Let the variables' meanings write the loop
| Variable | Always means, at index i after the updates |
|---|---|
l |
the sum of the numbers left of i: nums[0] to nums[i - 1] |
r |
the sum of the numbers right of i: nums[i + 1] to the end |
| Code | What happened | What it restores |
|---|---|---|
l = 0, r = sum(nums) |
the split is before index 0 | nothing is left of it; everything is right of it |
r -= nums[i] |
the split reached i |
nums[i] is the pivot itself, so it leaves the right side |
if i != 0: l += nums[i-1] |
the number just passed | it joins the left side; at index 0 nothing was passed |
if l == r: return i |
both sides are known | a balance is a pivot, and the first one is the leftmost |
return -1 |
the loop ended | no index balanced |
s = sum(nums) is never read, so removing it changes nothing.
The method carries over: write down which elements each running sum covers at index i, and each update is the element that just crossed the boundary.
Alternatives compared
| Approach | Time | Space | How it works |
|---|---|---|---|
| Brute force | O(n²) | O(1) | At each index, sum the numbers on each side from scratch. |
| Prefix-sum array | O(n) | O(n) | Store the sum up to each index; any index’s two sides are then two lookups. |
| Two running sums (chosen) | O(n) | O(1) | r starts at the total and l at 0. At each index, nums[i] leaves r and nums[i − 1] joins l. |
| One running sum | O(n) | O(1) | Keep only the left sum: the right sum is total − left − nums[i], so the test is 2 · left + nums[i] = total. |
The two running sums keep both sides of the test in plain view. Keeping one sum saves a variable, at the cost of a test that needs the identity above to read.
solution.py
class Solution:
def pivotIndex(self, nums: list[int]) -> int:
s = sum(nums)
l = 0
r = sum(nums)
for i in range(len(nums)):
r -= nums[i]
if i != 0:
l += nums[i-1]
if l == r:
return i
return -1Notes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.