
Description
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
Intuition
The pivot index in an array is the point where the sum of elements on the left side is equal to the sum of elements on the right side. The idea is to iterate through the array while keeping track of the cumulative sum from both ends. By doing this, we can efficiently determine if any index satisfies the condition where the left and right sums are equal.
Approach
- Prefix and Postfix Sums:
- First, create two auxiliary arrays,
prefix
andpostfix
. Theprefix
array will store the cumulative sum of elements from the left up to the current index, while thepostfix
array will store the cumulative sum of elements from the right up to the current index. - For theprefix
array, start with an initial value of0
and compute the cumulative sum as you traverse the array from left to right. - Similarly, populate thepostfix
array by traversing the array from right to left. - Finding the Pivot Index:
- After constructing the
prefix
andpostfix
arrays, iterate through the original array to check if any indexi
satisfies the condition whereprefix[i]
equalspostfix[i+1]
. - If such an index is found, return it as the pivot index. - Edge Cases:
- Handle edge cases where the pivot might be at the start or the end of the array. If no such index is found, return
-1
.
Complexity
Time Complexity:
The solution runs in O(n)
time, where n
is the length of the array. This is because we traverse the array a few times to build the prefix
and postfix
arrays and then perform a final pass to check for the pivot index.
Space Complexity:
The space complexity is O(n)
due to the additional space required for the prefix
and postfix
arrays.
Code
C++
class Solution {
public:
int pivotIndex(std::vector& nums) {
int len = nums.size();
std::vector prefix(len + 1, 0), postfix(len + 1, 0);
for (int i = 0; i < len; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (int i = len - 1; i >= 0; i--) {
postfix[i] = postfix[i + 1] + nums[i];
}
for (int i = 0; i < len; i++) {
if (prefix[i] == postfix[i + 1]) {
return i;
}
}
return -1;
}
};
Python
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
len_nums = len(nums)
prefix = [0] * (len_nums + 1)
postfix = [0] * (len_nums + 1)
for i in range(len_nums):
prefix[i + 1] = prefix[i] + nums[i]
for i in range(len_nums - 1, -1, -1):
postfix[i] = postfix[i + 1] + nums[i]
for i in range(len_nums):
if prefix[i] == postfix[i + 1]:
return i
return -1
Java
class Solution {
public int pivotIndex(int[] nums) {
int len = nums.length;
int[] prefix = new int[len + 1];
int[] postfix = new int[len + 1];
for (int i = 0; i < len; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (int i = len - 1; i >= 0; i--) {
postfix[i] = postfix[i + 1] + nums[i];
}
for (int i = 0; i < len; i++) {
if (prefix[i] == postfix[i + 1]) {
return i;
}
}
return -1;
}
}
JavaScript
var pivotIndex = function (nums) {
let len = nums.length, prefix = [0], postfix = new Array(len + 1).fill(0);
for (let n of nums) {
prefix.push(n + prefix.at(-1));
}
for (let i = len - 1; i >= 0; i--) {
postfix[i] = postfix[i + 1] + nums[i];
}
console.log("prefix: ", prefix);
console.log("postfix: ", postfix);
for (let i = 0; i < len; i++) {
if (prefix[i] === postfix[i + 1]) return i;
}
return -1;
};