Module 06 · Prefix Sums, Prefix State, and Difference Arrays

053. Pivot Index

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the earliest index whose elements strictly to its left and strictly to its right have equal sums. The pivot value is excluded from both sides. Empty input returns -1. Negative values are allowed.

Examples

Example 1

pivot_index([1, 7, 3, 6, 5, 6])
=> 3

Both strict sides sum to eleven.

Example 2

pivot_index([9])
=> 0

Both sides of the singleton are empty sums.

Example 3

pivot_index([])
=> -1

There is no candidate index.

Reveal the worked solution and reasoning

Why this mechanism works

With total sum known, the right sum can be derived from total-left-current. Keep only the sum strictly before the candidate and test before adding the candidate to it. This is a commit-before-ingest variation on the basic scan.

State and boundaries

left is the sum at indices smaller than i. total is the full input sum.

Protocol

Compute total.
Start left at zero.
Test left == total-left-value.
Return the first matching index.
Add value to left only after rejection.

Visualization

[1,7,3] | 6 | [5,6]
left=11        right=11
pivot index=3

Python implementation

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

pivot_index([1, 7, 3, 6, 5, 6])

L2 pivot_index: total = sum(nums)
nums=[1, 7, 3, 6, 5, 6]; total=28

L3 pivot_index: left = 0
nums=[1, 7, 3, 6, 5, 6]; total=28; left=0

L4 pivot_index: for i, value in enumerate(nums):
nums=[1, 7, 3, 6, 5, 6]; total=28; left=0; i=0; value=1

L7 pivot_index: left += value
nums=[1, 7, 3, 6, 5, 6]; total=28; left=1; i=0; value=1

L4 pivot_index: for i, value in enumerate(nums):
nums=[1, 7, 3, 6, 5, 6]; total=28; left=1; i=1; value=7

L7 pivot_index: left += value
nums=[1, 7, 3, 6, 5, 6]; total=28; left=8; i=1; value=7

L4 pivot_index: for i, value in enumerate(nums):
nums=[1, 7, 3, 6, 5, 6]; total=28; left=8; i=2; value=3

L7 pivot_index: left += value
nums=[1, 7, 3, 6, 5, 6]; total=28; left=11; i=2; value=3

L4 pivot_index: for i, value in enumerate(nums):
nums=[1, 7, 3, 6, 5, 6]; total=28; left=11; i=3; value=6

Result: 3. Both strict sides sum to eleven.

pivot_index([9])

L2 pivot_index: total = sum(nums)
nums=[9]; total=9

L3 pivot_index: left = 0
nums=[9]; total=9; left=0

L4 pivot_index: for i, value in enumerate(nums):
nums=[9]; total=9; left=0; i=0; value=9

Result: 0. Both sides of the singleton are empty sums.

Why the solution is correct

At each test, subtracting the left prefix and current value from total leaves exactly the right suffix. The equality is therefore the pivot condition. Increasing-index tests guarantee the earliest pivot is returned.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Adding the current value before the test includes it on the wrong side. Treating missing left or right sides as invalid wrongly rejects endpoint pivots.

Reasoning card

State: left is the sum at indices smaller than i. total is the full input sum.

Invariant: Before index i, left_sum equals values strictly left of i.

Decision to rehearse: Derive right sum from total and processed prefix.

Finish: Add value to left only after rejection

Transfer exercise

Return every pivot index, preserving the distinction between checking and extending the left prefix.