Find Pivot Index
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.
Two properties shape the solution. 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. Negative numbers are allowed, which means the running sum can decrease as we move right, ruling out any approach that assumes sums are monotonically increasing.
If we know the total sum of the array, then for any index i, the right sum is totalSum - leftSum - nums[i]. The pivot condition leftSum == rightSum becomes leftSum == totalSum - leftSum - nums[i], which simplifies to 2 * leftSum + nums[i] == totalSum. This can be checked 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 an O(n) solution is 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
For each index, compute the left sum and the right sum separately, then check if they are equal. This uses two inner loops for every candidate index: one summing the elements before i, one summing the elements after i.
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 recomputes the left sum from scratch at every index. Moving from index i to i+1 changes the left sum by a single element, but the inner loops discard that work. The next approach keeps a running left sum and derives the right sum from the total, dropping the cost to a single pass.
Approach 2: Prefix Sum (Optimal)
Intuition
Given the total sum of the entire array, the right sum at any index follows without a separate loop. At index i, the right sum is totalSum - leftSum - nums[i], so the pivot condition leftSum == rightSum becomes leftSum == totalSum - leftSum - nums[i].
Only two values are needed: the total sum (computed once upfront) and a running left sum built up while scanning from left to right. That is one pass to compute the total, then one pass to find the pivot.
At any index i, the array splits into three parts that together cover every element: the elements to the left (summing to leftSum), the element at i (nums[i]), and the elements to the right (summing to rightSum). So leftSum + nums[i] + rightSum = totalSum holds at every index, and rearranging gives rightSum = totalSum - leftSum - nums[i]. This identity is what lets the right sum be read off in O(1) instead of recomputed.
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.