Problem
Given an integer array nums, return the leftmost pivot index.The pivot index is the index where the sum of all elements strictly to the left is equal to the sum of all elements strictly to the right. If no such index exists, return
-1.
If the pivot index is
0, the left sum is 0. Similarly, if the pivot index is the last index, the right sum is 0.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
nums = [1,7,3,6,5,6]Output
3Example 2
Input
nums = [1,2,3]Output
-1Solution
Solution 1: Prefix Sum
This solution uses the Prefix Sum technique. First, we calculate the total sum of all elements in the array.As we traverse the array, we maintain the left sum. For each index, the right sum can be calculated as
totalSum - leftSum - nums[i]. If the left sum and right sum are equal, the current index is the pivot index.
class Solution {
public int pivotIndex(int[] nums) {
int totalSum = 0;
int leftSum = 0;
for (int num : nums) {
totalSum += num;
}
for (int i = 0; i < nums.length; i++) {
int rightSum = totalSum - leftSum - nums[i];
if (leftSum == rightSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}
}Solution 2: Suffix Sum
This approach uses a Suffix Sum array to store the sum of elements to the right of every index. We build thepost array from right to left, where post[i] represents the sum of all elements after index i.
We then traverse the array from left to right while maintaining the left sum. At each index, if the left sum is equal to
post[i], the current index is the pivot index.
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int[] post = new int[n];
for (int i = n - 2; i >= 0; i--) {
post[i] = nums[i + 1] + post[i + 1];
}
int sum = 0;
for (int i = 0; i < n; i++) {
if (sum == post[i]) {
return i;
}
sum += nums[i];
}
return -1;
}
}Complexity
Both solutions process the array in linear time, so the time complexity isO(n), where n is the length of the array.
Solution 1 uses only a few variables, so its extra space complexity is
O(1). Solution 2 uses an additional suffix sum array of size n, so its extra space complexity is O(n).