Find Pivot Index

Easy#724subarray sum

You get an array of numbers. Find the pivot index: the sum of the numbers strictly to its left equals the sum of the numbers strictly to its right, and an empty side sums to 0. If there are several, return the leftmost; if there is none, return -1. Our example: [3, -1, 4, 9, 2, 5, -1] — the answer is 3: left of the 9 is 3 - 1 + 4 = 6, right of it is 2 + 5 - 1 = 6.

724 Find Pivot IndexWalkthrough · 1×

Example: [3, -1, 4, 9, 2, 5, -1]. Under the numbers is left at every gap it reaches; under them, the sums of the two sides of i.

numsleft3-14925-1
not reached yetleft of i, in leftcurrentright of i, in rightthe pivot

Add up every number once: total = 21

01/18
restart · back · play · step
Speed
1function pivotIndex(nums):
2 total = sum(nums)
3 left = 0
4 for i from 0 to len(nums) - 1:
5 right = total - left - nums[i]
6 if left == right:
7 return i
8 left = left + nums[i]
9 return -1
state
total
21
left
–
i
–
right
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. For every i, left + nums[i] + right = total. So right = total − left − nums[i]: one sum up front gives the right side at every index without adding it up again.
  2. left grows by one number per step, so it is the running prefix sum, and no stretch is added up twice.
  3. The check comes before nums[i] joins left, so the number at i counts on neither side. Indices are tried from left to right, so the first match is the leftmost pivot.

Complexity

Time O(n): one pass for the total and one for the pivot. Memory O(1): only total and left, no array of prefix sums.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.