Approach 1: O(n) space
Calculate the right sum (suffix sum) for each index and store it in an array. Then iterate through the original array keeping a track of the left sum (prefix sum). Whenever both the sums become equal, return the index. If no such index is found, return -1.
int pivotIndex(vector<int>& nums) {
int n = nums.size();
vector<int> rSum(n, 0);
int sum = 0;
for(int i=n-1; i>=0; i--) {
rSum[i] = sum;
sum+=nums[i];
}
sum = 0;
for (int i=0; i<n; i++) {
if (sum==rSum[i]) return i;
sum+=nums[i];
}
return -1;
}
Time complexity: O(n)
Space complexity: O(n)
Approach 2: O(1) space
We don’t really need to store the right sum (suffix sum) in an extra array. We could calculate the sum of all elements and then decrease it as we process the array from left to right.
int pivotIndex(vector<int>& nums) {
int rSum = accumulate(nums.begin(), nums.end(), 0);
int lSum = 0;
for (int i=0; i<nums.size(); i++) {
rSum -= nums[i];
if (lSum==rSum) return i;
lSum += nums[i];
}
return -1;
}
Time complexity: O(n)
Space complexity: O(1)