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;
}