Find Pivot Index
Problem
Given an integer array nums, return the pivot index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, return -1.
- 1 ≤ nums.length ≤ 10⁴
- −1000 ≤ nums[i] ≤ 1000
Example
nums = [1, 7, 3, 6, 5, 6]3The pivot index is 3 because the sum of elements to the left (1 + 7 + 3 = 11) equals the sum of elements to the right (5 + 6 = 11). The algorithm starts by calculating the total sum of the array (28). It then iterates through the array, maintaining a running left sum. At index 0, left sum is 0 and right sum is 28 - 1 = 27, which are not equal. At index 1, left sum is 1 and right sum is 27 - 7 = 20, still not equal. This continues until index 3, where left sum is 11 and right sum is 11, satisfying the condition and returning 3.
Approach
Straightforward Solution
A brute-force approach would compute the sum of elements to the left and right of every index separately, resulting in O(n^2) time complexity, which is inefficient for large arrays.
Core Observation
The pivot index is defined by the equality of the sum of elements on its left and right. The total sum of the array can be used to compute the right sum at any index by subtracting the left sum and the current element.
Path to Optimal
By precomputing the total sum of the array, the right sum at any index can be derived by subtracting the left sum and the current element from the total sum. This allows checking the pivot condition in a single pass with O(n) time complexity.
Optimal Approach
Initialize left_sum to 0 and right_sum to the total sum of the array. Iterate through the array, decrementing right_sum by the current element and checking if left_sum equals right_sum. If they are equal, return the current index. Otherwise, add the current element to left_sum and continue. If no pivot index is found, return -1.
Time
O(n)
The algorithm computes the total sum once and then iterates through the array once, performing constant-time operations per element.
Space
O(1)
Only a few integer variables are used to track sums and indices, with no additional data structures proportional to input size.
Pattern Spotlight
Prefix Sum
When a problem requires comparing sums of subarrays repeatedly, precompute the total sum and maintain a running prefix sum to enable constant-time calculation of complementary sums, reducing nested loops to a single pass.
Solution
| 1 | class Solution: |
| 2 | def pivotIndex(self, nums: List[int]) -> int: |
| 3 | left_sum = 0 |
| 4 | right_sum = sum(nums) |
| 5 | |
| 6 | for index, val in enumerate(nums): |
| 7 | right_sum -= val |
| 8 | if left_sum == right_sum: |
| 9 | return index |
| 10 | left_sum += val |
| 11 | |
| 12 | return -1 |
Step-by-Step Solution
Initialize Left and Right Sums for Pivot Detection
| 3 | left_sum = 0 |
| 4 | right_sum = sum(nums) |
Objective
To set up the initial sums needed to compare left and right partitions at each index.
Key Insight
Calculating the total sum upfront allows the algorithm to derive the right sum dynamically by subtracting the current element and the accumulated left sum. Starting left_sum at zero reflects that no elements are to the left of the first index.
Interview Quick-Check
Core Logic
Precompute total sum to enable O(1) calculation of right sum at each index by subtracting left_sum and current element.
State & Boundaries
Initialize left_sum to 0 before iteration to represent the sum of elements left of the first index.
Iterate Through Array to Identify Pivot Index
| 6 | for index, val in enumerate(nums): |
| 7 | right_sum -= val |
| 8 | if left_sum == right_sum: |
| 9 | return index |
| 10 | left_sum += val |
Objective
To traverse the array, update sums, and check for the pivot condition at each index.
Key Insight
At each index, the right sum is updated by removing the current element from the total sum. Comparing left_sum and right_sum immediately after this update checks if the current index is the pivot. Updating left_sum after the check prepares for the next iteration. This order ensures the current element is excluded from both sums correctly.
Interview Quick-Check
Core Logic
Update right_sum by subtracting current element before comparison to exclude it from the right partition, then compare with left_sum to find pivot.
State & Boundaries
Add current element to left_sum after comparison to maintain correct sums for subsequent indices.
Common Pitfalls & Bugs
Failing to subtract current element from right_sum before comparison leads to incorrect pivot detection.
Return -1 When No Pivot Index Exists
| 12 | return -1 |
Objective
To signal that no index satisfies the pivot condition after full traversal.
Key Insight
If the loop completes without returning, it means no index was found where left and right sums are equal. Returning -1 explicitly communicates the absence of a valid pivot index.
Interview Quick-Check
Core Logic
Return -1 after full iteration to indicate no pivot index was found.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
right_sum -= valSubtract the current element from right_sum to exclude it from the right partition.
This update ensures right_sum accurately reflects the sum of elements strictly to the right of the current index, which is essential for correct pivot comparison.
if left_sum == right_sum:Check if left_sum equals right_sum to identify the pivot index.
This equality check is the core condition defining the pivot index; detecting this condition immediately allows early return for efficiency.
right_sum = sum(nums)Calculate the total sum of the array to represent the initial right sum.
Precomputing the total sum allows the algorithm to derive the right sum at any index by subtracting left_sum and the current element, enabling O(1) right sum calculation per iteration.
left_sum += valAdd the current element to left_sum to update the left partition sum for the next iteration.
Updating left_sum after the pivot check maintains the correct sum of elements to the left of the next index, preserving the invariant for subsequent comparisons.
return indexReturn the current index as the pivot index when left and right sums are equal.
Returning immediately upon finding the pivot index prevents unnecessary further computation and satisfies the problem requirement to return the leftmost pivot.
left_sum = 0Initialize left_sum to zero to represent the sum of elements to the left of the current index.
Starting left_sum at zero correctly models that no elements exist to the left of the first index, establishing the baseline for incremental sum updates.
return -1Return -1 to indicate no pivot index exists in the array.
Explicitly returning -1 signals that the algorithm exhaustively checked all indices without finding a valid pivot, fulfilling the problem's requirement.
for index, val in enumerate(nums):Begin iterating through the array with index and value.
Enumerating both index and value is necessary to update sums and check the pivot condition at each position.
Test Your Understanding
Why does subtracting the current element from the total sum give the right sum at the current index?
Because the total sum includes all elements, subtracting the left sum and the current element leaves the sum of elements to the right of the current index.
Related Problems
Prefix Sum pattern
Don't just read it. Drill it.
Reconstruct Find Pivot Index from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find Pivot Index drill