#724
Find Pivot Index
Easy Total minus left
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the leftmost index where the sum of everything to its left equals the sum of everything to its right. Return -1 if none.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the first index where the left total equals the right total.
Why this works: right total = total - left - current, so one running left sum is enough.
Example: [1, 7, 3, 6, 5, 6], total 28
i=0: left 0, right 27i=1: left 1, right 20i=2: left 8, right 17i=3: left 11, right 11 → index 3
✦Hints open one at a time
Compute the total once.
right sum = total - left sum - nums[i].
↗Approach
Walk left to right keeping the left sum. At each index check whether leftSum equals total - leftSum - nums[i], then add nums[i] to leftSum.
</>Solution (Java)
class Solution {
public int pivotIndex(int[] nums) {
int total = 0;
for (int x : nums) total += x;
int left = 0;
for (int i = 0; i < nums.length; i++) {
if (left == total - left - nums[i]) return i; // check before adding nums[i]
left += nums[i];
}
return -1;
}
}!Common mistake
Adding nums[i] to the left sum before the check, which counts the pivot on the left side.
Complexity
- Time: O(n).
- Space: O(1).
