Dare2Solve
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.
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.
Prefix and Postfix Sums:
prefix
and postfix
. The prefix
array will store the cumulative sum of elements from the left up to the current index, while the postfix
array will store the cumulative sum of elements from the right up to the current index.prefix
array, start with an initial value of 0
and compute the cumulative sum as you traverse the array from left to right.postfix
array by traversing the array from right to left.Finding the Pivot Index:
prefix
and postfix
arrays, iterate through the original array to check if any index i
satisfies the condition where prefix[i]
equals postfix[i+1]
.Edge Cases:
-1
.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.
The space complexity is O(n)
due to the additional space required for the prefix
and postfix
arrays.
class Solution {
public:
int pivotIndex(std::vector<int>& nums) {
int len = nums.size();
std::vector<int> 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;
}
};
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
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;
}
}
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;
};