Find Pivot Index
Find the position where the sum of everything to its left equals the sum of everything to its right, in one pass, using a running total.
Updated Short read: 4 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Running total | O(n) | O(1) |
The problem
Given an array of integers, return the pivot index: the position where the sum of all the numbers to its left equals the sum of all the numbers to its right. The number at the pivot itself belongs to neither side. If there are several pivots, return the leftmost. If there are none, return -1.
A side with no numbers in it has a sum of 0, so the first or last position can be a pivot.
[1, 7, 3, 6, 5, 6] → 3 (1 + 7 + 3 = 11 on the left, 5 + 6 = 11 on the right)
[1, 2, 3] → -1
[2, 1, -1] → 0 (nothing on the left; 1 + -1 = 0 on the right)Approach 1: brute force
For each position, add up the left side and the right side and compare.
JavaScript
function pivotIndexBruteForce(numbers) {
for (let i = 0; i < numbers.length; i++) {
let leftSum = 0;
for (let j = 0; j < i; j++) leftSum += numbers[j];
let rightSum = 0;
for (let j = i + 1; j < numbers.length; j++) rightSum += numbers[j];
if (leftSum === rightSum) return i;
}
return -1;
}Python
def pivot_index_brute_force(numbers):
for i in range(len(numbers)):
left_sum = sum(numbers[:i])
right_sum = sum(numbers[i + 1 :])
if left_sum == right_sum:
return i
return -1Time O(n²): every position adds up almost the whole array again. Space O(1).
Approach 2: running total
Moving from one position to the next barely changes the two sums: one number joins the left side and one leaves the right. Recalculating both from scratch throws that away. This is the situation prefix sums are for.
Only two numbers are needed:
total: the sum of the whole array, worked out once.leftSum: the sum of everything before the current position, updated as the loop moves.
The right side then needs no loop at all, because the three parts add up to the total:
leftSum + numbers[i] + rightSum = total
rightSum = total − leftSum − numbers[i]JavaScript
function pivotIndex(numbers) {
let total = 0;
for (const value of numbers) total += value;
let leftSum = 0;
for (let i = 0; i < numbers.length; i++) {
const rightSum = total - leftSum - numbers[i];
if (leftSum === rightSum) return i;
leftSum += numbers[i];
}
return -1;
}Python
def pivot_index(numbers):
total = sum(numbers)
left_sum = 0
for i, value in enumerate(numbers):
right_sum = total - left_sum - value
if left_sum == right_sum:
return i
left_sum += value
return -1Walkthrough
[1, 7, 3, 6, 5, 6], where total is 28:
| i | numbers[i] | leftSum | rightSum = 28 − leftSum − numbers[i] | Equal? |
|---|---|---|---|---|
| 0 | 1 | 0 | 27 | No |
| 1 | 7 | 1 | 20 | No |
| 2 | 3 | 8 | 17 | No |
| 3 | 6 | 11 | 11 | Yes: return 3 |
Time O(n): one pass for the total and one to find the pivot. Space O(1): no prefix array is stored, because each position only needs the total so far.
Why the order of the two lines matters
Inside the loop, the comparison comes before leftSum += numbers[i]. At the moment of the comparison, leftSum must hold the sum of the numbers strictly before position i.
Swap the two lines and leftSum already includes numbers[i], so the pivot's own value is counted on the left and subtracted a second time on the right. For [1, 7, 3, 6, 5, 6] at index 3, the left would be 17 and the right 5, and the pivot would be missed.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(pivotIndex([1, 7, 3, 6, 5, 6])); // 3
console.log(pivotIndex([1, 2, 3])); // -1Python
print(pivot_index([1, 7, 3, 6, 5, 6])) # 3
print(pivot_index([1, 2, 3])) # -1The comment after each line is the result you should see.
Common mistakes
- Counting the pivot's own value on one of the sides. It belongs to neither.
- Updating
leftSumbefore comparing. See above. - Starting the loop at index 1 or stopping one early. Both ends can be pivots, because an empty side sums to 0.
[2, 1, -1]has its pivot at index 0. - Assuming the numbers are positive. With negative numbers the sums do not grow steadily, so the loop cannot stop early when the left side becomes larger than the right.
- Returning the last pivot found. The problem asks for the leftmost, so return as soon as one is found.
Original problem: LeetCode 724: Find Pivot Index