Solution For Find Pivot Index
Problem Statement:
Given an array of integers nums, calculate the pivot index of the 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 applies to the right edge of the array as well.
If there is no such index, the function should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.
Example:
Input: nums = [1,7,3,6,5,6] Output: 3 Explanation: The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the leftmost pivot index.
Solution:
The easiest approach to solve this problem is to compute the total sum of the array first. Then traverse through the array, checking at each index if the sum of all the elements to its left is equal to the sum of all the elements to its right.
If yes, then return that index as the pivot index. If no such index is found, then return -1.
Let’s implement this approach in code:
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total_sum = sum(nums)
left_sum = 0
for i, num in enumerate(nums):
if left_sum == total_sum – left_sum – num:
return i
left_sum += num
return -1
Time Complexity:
The time complexity of this solution is O(n), where n is the length of the input array. We traverse through the array only once.
Space Complexity:
The space complexity of this solution is O(1), as we are not using any extra space except for a few variables to store the sum values and the loop index.
Step by Step Implementation For Find Pivot Index
class Solution { public int pivotIndex(int[] nums) { // edge case if (nums.length == 0) { return -1; } // initializations int leftSum = 0; int rightSum = 0; // calculate rightSum for (int i = 1; i < nums.length; i++) { rightSum += nums[i]; } // iterate through array for (int i = 0; i < nums.length; i++) { // if leftSum == rightSum, then we have found the pivot index if (leftSum == rightSum) { return i; } // update leftSum and rightSum leftSum += nums[i]; if (i + 1 < nums.length) { rightSum -= nums[i + 1]; } } // if we get to this point, then there is no pivot index return -1; } }
class Solution: def pivotIndex(self, nums: List[int]) -> int: # edge case for lists with no elements or only one element if len(nums) == 0: return -1 if len(nums) == 1: return 0 # initialize left and right sums to keep track of the sums of elements to the left and right of the current index left_sum = 0 right_sum = sum(nums[1:]) # iterate through the list for i in range(len(nums)): # if the left sum is equal to the right sum, we have found the pivot index if left_sum == right_sum: return i # otherwise, update the left and right sums else: # if we are at the last index, we can't update the right sum anymore if i == len(nums) - 1: return -1 else: left_sum += nums[i] right_sum -= nums[i+1] # if we reach this point, it means that we didn't find a pivot index return -1
/** * @param {number[]} nums * @return {number} */ //Given an array of integers nums, write a method that returns the "pivot" index of this array. //We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. //If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index. var pivotIndex = function(nums) { let sum = 0; let leftSum = 0; for(let i = 0; i < nums.length; i++){ sum += nums[i]; } for(let i = 0; i < nums.length; i++){ sum -= nums[i]; if(leftSum === sum){ return i; } leftSum += nums[i]; } return -1; };
int pivotIndex(vector& nums) { int sum = 0, leftsum = 0; for (int x: nums) sum += x; for (int i = 0; i < nums.size(); ++i) { if (leftsum == sum - leftsum - nums[i]) return i; leftsum += nums[i]; } return -1; }
public int PivotIndex(int[] nums) { //edge case if(nums.Length == 0){ return -1; } //sum left and right of each index int[] leftSum = new int[nums.Length]; int[] rightSum = new int[nums.Length]; //initialize first values of each sum array leftSum[0] = 0; rightSum[nums.Length - 1] = 0; //calculate the sums for(int i = 1; i < nums.Length; i++){ leftSum[i] = leftSum[i-1] + nums[i-1]; } for(int j = nums.Length - 2; j >= 0; j--){ rightSum[j] = rightSum[j+1] + nums[j+1]; } //compare sums to find the pivot index for(int k = 0; k < nums.Length; k++){ if(leftSum[k] == rightSum[k]){ return k; } } //if no pivot index is found return -1; }