Find Pivot Index
Last Updated: March 29, 2026
Understanding the Problem
We need to find an index in the array where everything to its left adds up to the same value as everything to its right. The element at the pivot index itself is not included in either sum.
A couple of things to notice. First, the left sum for index 0 is 0 (nothing to the left), and the right sum for the last index is 0 (nothing to the right). So edge indices are valid candidates. Second, negative numbers are allowed, which means the running sum can decrease as we move right. This rules out any approach that assumes sums are monotonically increasing.
The key observation is this: if we know the total sum of the array, then for any index i, the right sum is just totalSum - leftSum - nums[i]. So the pivot condition becomes leftSum == totalSum - leftSum - nums[i], which simplifies to 2 * leftSum + nums[i] == totalSum. We can check this in a single pass.
Key Constraints:
1 <= nums.length <= 10^4→ With n up to 10,000, even O(n^2) would pass (100 million operations is borderline). But O(n) is clearly preferred and achievable here.-1000 <= nums[i] <= 1000→ Values can be negative. This means sums can decrease, and multiple pivot indices could theoretically exist (we return the leftmost). The bounded range also means the total sum fits comfortably in a 32-bit integer (max ~10^7).
Approach 1: Brute Force
Intuition
The most natural starting point: for each index, compute the left sum and the right sum separately, then check if they're equal. This means two inner loops for every candidate index, which is simple but repetitive.
Algorithm
- Iterate through each index
ifrom 0 to n-1. - For each
i, compute the left sum by adding all elements from index 0 to i-1. - Compute the right sum by adding all elements from index i+1 to n-1.
- If the left sum equals the right sum, return
i. - If no pivot is found after checking all indices, return -1.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n indices, we iterate through up to n elements to compute the left and right sums.
- Space Complexity: O(1). We only use a few integer variables. No additional data structures.
This works, but we're recomputing the left sum from scratch at every index. When we move from index i to i+1, the left sum only changes by one element, yet we throw away all that work.
What if we maintained a running left sum and derived the right sum from the total?
Approach 2: Prefix Sum (Optimal)
Intuition
Here's the insight that makes this problem simple. If you know the total sum of the entire array, you can derive the right sum at any index without a separate loop. At index i, the right sum is just totalSum - leftSum - nums[i]. So the pivot condition leftSum == rightSum becomes leftSum == totalSum - leftSum - nums[i].
This means we only need two things: the total sum (computed once upfront) and a running left sum that we build up as we scan from left to right. That's two passes total, or really one pass after the initial sum.
The total sum of the array is fixed. At any index i, the array is split into three parts: elements to the left (summing to leftSum), the element at i (nums[i]), and elements to the right (summing to rightSum). Since these three parts cover the entire array, we know leftSum + nums[i] + rightSum = totalSum. Rearranging gives us rightSum = totalSum - leftSum - nums[i].
By maintaining leftSum as a running total, we avoid recomputing it from scratch at each index. We just add nums[i] to leftSum after checking the pivot condition, which prepares it for the next iteration.
Algorithm
- Compute the total sum of the entire array.
- Initialize
leftSum = 0. - Iterate through each index
i: - Compute rightSum as
totalSum - leftSum - nums[i]. - If
leftSum == rightSum, returni. - Add
nums[i]toleftSum(preparing for the next index). - If no pivot index was found, return -1.
Example Walkthrough
Code
- Time Complexity: O(n). One pass to compute the total sum, one pass to find the pivot. Each pass touches every element exactly once.
- Space Complexity: O(1). Only a few integer variables (
totalSum,leftSum,rightSum). No arrays or data structures.