DSAMotivator

Find Pivot Index

Easy·➕ Prefix Sum·Open on LeetCode ↗

Find the leftmost position where everything to its left sums to the same total as everything to its right.

nums = [4, 2, 5, 8, 6, 5]step 1/5
4
2
5
8
6
5
0
1
2
3
4
5
sums
total
30

The whole array sums to 30. That one number makes every right side free.

1def pivot_index(nums):
2    total = sum(nums)
3    left = 0
4    for i, n in enumerate(nums):
5        if left == total - left - n:
6            return i
7        left += n
8    return -1
Read the 5 steps as text
  1. 1The whole array sums to 30. That one number makes every right side free.
  2. 2Left is 0, right is 26. Not balanced.
  3. 3Left is 4, right is 24. Not balanced.
  4. 4Left is 6, right is 19. Not balanced.
  5. 5Left is 11 and right is 11. They match — index 3 is the pivot.

The idea

Computing both sides from scratch at every index re-adds the same numbers over and over — O(n²) for a question that clearly shouldn't need it.

The saving is that the right side is not independent information. Once you know the total of the whole array and the sum of everything to the left, the right side is forced: right = total − left − nums[i].

So one pass to get the total, then one pass carrying a running left sum, and each index is checked in constant time. This is the prefix-sum pattern in its smallest form — the observation that a running total turns a range query into a subtraction.

Note the algorithm never actually builds a prefix array. It only needs the prefix at the current position, so a single variable suffices.

The approach

  1. 1Sum the whole array once.
  2. 2Walk left to right keeping `left`, the sum of everything strictly before the current index.
  3. 3The right side is total − left − current, with no work required.
  4. 4Return the first index where the two sides match, or −1 if none do.

Complexity

Time
O(n)
Space
O(1)

Two passes, one accumulator. Building an explicit prefix array is the same time but O(n) space for no gain here.

Code

def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, n in enumerate(nums):
        if left == total - left - n:
            return i
        left += n
    return -1

What goes wrong

  • •Including the pivot itself on one side. It belongs to neither — subtracting `nums[i]` as well as `left` is what excludes it.
  • •Adding the current value to `left` before the comparison, which shifts every check one place.
  • •Assuming the array is positive and stopping early when `left` exceeds half the total. Negative numbers make that reasoning wrong, and these problems very often include them.
  • •Returning any valid index. The leftmost one is asked for, so return on the first match rather than collecting them.