Find Pivot Index
Given an array of integers nums
Example 1
Output: 3
Explanation: left sum 1 + 7 + 3 = 11, right sum 5 + 6 = 11.
Example 2
Output: -1
Example 3
Output: 0
Explanation: left sum 0 (nothing to the left), right sum 1 + (-1) = 0.
How to Think About It
Step 1: The simple way
For each index, add up both sides from scratch: O(n²).
Step 2: The right sum follows from the left sum
Compute the total once. At index iiii
right = total - left - nums[i]
Step 3: Keep the left sum running
Walk from the left. Before moving past index ileftrightnums[i]left
Walkthrough
nums = [1, 7, 3, 6, 5, 6]
| i | nums[i] | left | right = 28 - left - nums[i] | Equal? |
|---|---|---|---|---|
| 0 | 1 | 0 | 27 | no |
| 1 | 7 | 1 | 20 | no |
| 2 | 3 | 8 | 17 | no |
| 3 | 6 | 11 | 11 | yes: return 3 |
Java Solution
The left sum is updated after the comparison, so it never includes nums[i]
public class FindPivotIndex {
public static int pivotIndex(int[] nums) {
int total = 0;
for (int x : nums) {
total += x;
}
int left = 0; // sum of nums[0..i-1]
for (int i = 0; i < nums.length; i++) {
int right = total - left - nums[i]; // sum of nums[i+1..n-1]
if (left == right) {
return i;
}
left += nums[i];
}
return -1;
}
public static void main(String[] args) {
System.out.println(pivotIndex(new int[] {1, 7, 3, 6, 5, 6})); // 3
System.out.println(pivotIndex(new int[] {1, 2, 3})); // -1
System.out.println(pivotIndex(new int[] {2, 1, -1})); // 0
}
}
The original implementation,
Complexity
- Time: O(n): one pass for the total and one for the search.
- Space: O(1).
Running sums like this are prefix sums;