{ }SolveLogs
⌕
Home / Arrays & Hashing / #724
LeetCode #724 Easy

Find Pivot Index

Find Pivot Index is LeetCode 724 (Easy). Given an integer array nums, return its pivot index: the index where the sum of the numbers strictly to its left equals the sum of the numbers strictly to its right.

  • The number at the pivot itself counts on neither side.
  • If several indices qualify, return the leftmost one. If none does, return -1.
  • Values can be negative.

With up to 10,000 numbers, adding up both sides again at every index costs about 10⁸ additions, so the target is one linear pass.

Constraints
  • 1 <= nums.length <= 10⁴
  • -1000 <= nums[i] <= 1000
arrayprefix-sum
Open on LeetCode ↗
02

Intuition

Around any index i, the three parts always add up to the same number:

left + nums[i] + right = total

So once the total of the whole array is known, the right sum needs no loop at all: it is total - left - nums[i]. This is a prefix sum trick that keeps only one running sum instead of a whole prefix array.

The search becomes a single sweep. Keep left, the sum of everything before i. At each index, work out the right sum from it and compare the two. The scan runs from index 0 upward, so the first index where they match is the leftmost pivot.

How to spot this pattern

Any question that compares the part of an array before a position with the part after it can use the total: one running sum gives the left part, and subtraction gives the right part.

03

Approach

Try it first

Before reading on: if you already know the total of the array and the sum of everything left of index i, how do you get the sum to its right without another loop? Aim for O(n) time and O(1) space.

1

Add up the whole array once

Compute total = sum(nums) before the loop. Every right sum is worked out from this one number, so the array never has to be added up again.

2

Work out the right sum by subtraction

At index i, set right = total - left - nums[i]. Subtracting nums[i] takes the pivot out of the right side, because the pivot belongs to neither side.

3

Compare, then move the number to the left side

If left == right, return i at once; nothing earlier matched, so it is the leftmost pivot. Otherwise add nums[i] to left, because index i sits to the left of every index still to come.

4

Return -1 when the loop ends

If no index matched, no position splits the array into two equal sides, so the answer is -1.

04

Find Pivot Index solution in Python | C++ | Java

▶1class Solution:
▶2 def pivotIndex(self, nums):
▶3 total = sum(nums)
▶4 left = 0
▶5 for i, num in enumerate(nums):
▶6 right = total - left - num
▶7 if left == right:
▶8 return i
▶9 left += num
▶10 return -1
nums10713263546528totaltotal of all 6 numbers = 28
total28sum of [1, 7, 3, 6, 5, 6]
left0nothing seen yet
Add up the whole array once: total = 28. For any index, left + nums[i] + right equals this total, so every right sum can be found by subtraction instead of another loop.
nums107132635465right 2728total−0left−1nums[i]=27right0left≠27rightindex 0: left 0 ≠ right 27
i0nums[i] = 1
left0empty side
right2728 − 0 − 1
Try index 0. Nothing lies to its left, so left is 0. The right sum is total − left − nums[i] = 28 − 0 − 1 = 27; the 1 is taken out because the pivot sits on neither side. 0 and 27 differ, so index 0 is not the pivot.
nums107132635465left 10left+1nums[i]=1new left0left≠27rightmove 1 to the left side → left sum 1
left10 + 1
Index 0 is to the left of every index still to come, so its 1 joins the left sum, which becomes 1. The test comes first and the add second, so a number is never on the left side of its own test.
nums107132635465left 1right 2028total−1left−7nums[i]=20right1left≠20rightindex 1: left 1 ≠ right 20
i1nums[i] = 7
left1sum of indices 0 to 0
right2028 − 1 − 7
Try index 1. The right sum is total − left − nums[i] = 28 − 1 − 7 = 20; the 7 is taken out because the pivot sits on neither side. 1 and 20 differ, so index 1 is not the pivot.
nums107132635465left 81left+7nums[i]=8new left1left≠20rightmove 7 to the left side → left sum 8
left81 + 7
Index 1 is to the left of every index still to come, so its 7 joins the left sum, which becomes 8.
nums107132635465left 8right 1728total−8left−3nums[i]=17right8left≠17rightindex 2: left 8 ≠ right 17
i2nums[i] = 3
left8sum of indices 0 to 1
right1728 − 8 − 3
Try index 2. The right sum is total − left − nums[i] = 28 − 8 − 3 = 17; the 3 is taken out because the pivot sits on neither side. 8 and 17 differ, so index 2 is not the pivot.
nums107132635465left 118left+3nums[i]=11new left8left≠17rightmove 3 to the left side → left sum 11
left118 + 3
Index 2 is to the left of every index still to come, so its 3 joins the left sum, which becomes 11.
nums107132635465left 11right 1128total−11left−6nums[i]=11right11left=11rightindex 3: left 11 = right 11
i3nums[i] = 6
left11sum of indices 0 to 2
right1128 − 11 − 6
Try index 3. The right sum is total − left − nums[i] = 28 − 11 − 6 = 11; the 6 is taken out because the pivot sits on neither side. Left and right are both 11, so index 3 balances.
nums107132635465left 11right 1128total−11left−6nums[i]=11right11left=11rightfirst match → return 3
answer3
Return 3 without looking further. Every smaller index was tested and failed, so this is the leftmost pivot the problem asks for.
05

Common pitfalls

Adding the number to the left sum before the test

✗ Wrong
left += num
if left == total - left - num:
    return i
✓ Right
if left == total - left - num:
    return i
left += num

Now left already holds nums[i], so the pivot is counted on the left side. On [1,7,3,6,5,6] index 3 compares 17 with 5 instead of 11 with 11, and the code returns -1 instead of 3.

Leaving the pivot in the right sum

✗ Wrong
if left == total - left:
✓ Right
if left == total - left - num:

total - left still contains nums[i]. On [2,1,-1] index 0 compares 0 with 2 instead of 0 with 0, so the real pivot is missed and the code returns -1.

Stopping once the left sum is bigger

✗ Wrong
if left > right:
    break
✓ Right
keep scanning to the last index

That shortcut only holds when every number is positive. Negatives can shrink the left sum again: on [-1,-1,-1,-1,-1,0] index 0 already has left 0 above right -4, yet index 2 is a pivot (-2 and -2).

06

Edge cases

A single number, such as [7]

Both sides are empty and an empty side sums to 0, so index 0 is the pivot.

Pivot at the last index, such as [-1,1,5]

At index 2 the left sum is -1 + 1 = 0 and the right side is empty, also 0, so the answer is 2. No special case is needed.

07

Complexity

Time
O(n)
Space
O(1)
One pass adds up the total and a second pass tests each index once. Only total, left and right are stored, not a prefix array.
08

Find Pivot Index FAQ

LeetCode 724 and 1991: are they the same problem?

Yes. Find Pivot Index (724) and Find the Middle Index in Array (1991) have exactly the same rules, including returning the leftmost index, so this code passes both.

What is an equilibrium index?

It is another name for the same idea: a position where the sum before it equals the sum after it. Some versions number positions from 1 instead of 0, so check which one the task expects before returning.

Why not build a prefix sum array?

It works: store prefix[i] and read the right sum as prefix[n] - prefix[i + 1]. It needs O(n) extra memory, though, and the total already gives the same right sum with one variable.

← Prev · #721
Accounts Merge
Next · #733 →
Flood Fill