Find Pivot Index

There are countless ways to approach this problem and optimize your solution. In this article, we’ll explore one of those strategies to tackle this problem. Let’s see the problem statement first.

Problem Statement:

Given an array of integers nums, calculate the pivot index of this array. Return the leftmost pivot index. If no such index exists, return -1.

Pivot Index:

• 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.

Approach 1: Prefix Sum

So the idea is to subtract the known left sum and the current element from the total sum of the input array. By iterating through the input array and comparing the left sum and right sum at each index, we can identify the pivot index efficiently.

1. We first calculate the sum of all elements in the given array. This is done by iterating through the array and adding each element to the totalSum variable.

2. We then initialize a variable leftSum to keep track of the sum of elements to the left of the current index.

3. Next, we iterate through the array using a loop. For each element at the index i, we calculate the rightSum as the difference between the totalSum, leftSum, and the current element nums[i]. The rightSum represents the sum of elements to the right of the current index.

4. Now we compare leftSum and rightSum. If they are equal, it means we have found the pivot index, so we return the current index i.

5. If the pivot index is not found, we update leftSum by adding the current element nums[i] to it and continue to the next iteration.

6. If no pivot index is found after the loop, we return -1 to indicate that there is no pivot index in the array.

// ES6 Arrow Function
const pivotIndex = nums => {
    let totalSum = 0;
    for(let i of nums) totalSum += i;

    let leftSum = 0;
    for(let i = 0; i < nums.length; i++) {
        const rightSum = totalSum - leftSum - nums[i];
        if(leftSum === rightSum) return i;

        leftSum += nums[i];
    }

    return -1;
}

Time Complexity: O(N)

We have two loops, both used to iterate the input array of size N. Therefore, the time complexity is linear.

Space Complexity: O(1)

Since the space doesn’t belong to the size of the input array, it is constant.

I hope this article has provided you with valuable insights and helped you better understand this problem. Happy coding!

Problem - Leetcode 724