1. Find Pivot Index (LeetCode)
Model answer
The task
Given an integer array, return the leftmost index where the sum of the elements before it equals the sum of the elements after it. Return -1 if no such index exists.
Key idea
Compute the total sum once, then scan from left to right while maintaining the sum to the left. At each index, the right sum is the total minus the left sum and the current element.
Approach
- Sum all elements to get the total.
- Initialize the running left sum to zero.
- For each index, compare the left sum with
total - left_sum - nums[index]. - Return the index when the sums match; otherwise, add the current value to the left sum.
- Return
-1if the scan finishes without a match.
from typing import List
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total = sum(nums)
left_sum = 0
for i, value in enumerate(nums):
right_sum = total - left_sum - value
if left_sum == right_sum:
return i
left_sum += value
return -1
Complexity:
- Time: O(n), for one pass through the array after summing it.
- Space: O(1), using only a fixed number of extra variables.
Common follow-ups
- What if there are multiple pivot indices? The left-to-right scan returns the first; collect each matching index instead if all are required.
- Can this handle negative values? Yes. The equality check relies on sums, not on values being positive.
- What if the array is updated repeatedly? A single update changes the sums for many indices; a Fenwick tree or segment tree can support range-sum queries and updates more efficiently.