Find Pivot Index

Problem Statement

In the problem, we are provided with an array of integers named nums. The task is to determine the pivot index of this array. A pivot index refers to a position where the sum of all elements to the left of the index is exactly equal to the sum of all the elements to the right of the index. If the index happens to be at either end of the array, the sum of elements on the non-existent side is considered to be zero. The solution should return the leftmost pivot index if it exists; otherwise, it should return -1 if there is no such index that meets the criteria.

Examples

Example 1

Input:

nums = [1,7,3,6,5,6]

Output:

3

Explanation:

The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2

Input:

nums = [1,2,3]

Output:

-1

Explanation:

There is no index that satisfies the conditions in the problem statement.

Example 3

Input:

nums = [2,1,-1]

Output:

0

Explanation:

The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

Approach and Intuition

To solve the problem of finding the pivot index, one can follow a straightforward method involving prefix sums:

1. First, compute the total sum of all the elements in the array, referred to as total_sum.
2. Initialize a variable left_sum to zero. This variable will keep track of the sum of elements to the left of the current index as we iterate through the array.
3. Iterate through each index of the array:
   • Calculate the right sum by subtracting left_sum and the current element from total_sum.
   • Check if left_sum equals right_sum. If they are equal, then the current index is a pivot index. Return this index as the result.
   • If no pivot index is found during the iteration, increment left_sum by the value of the current element (this is preparation for the next iteration).
4. If the loop completes without finding any pivot index, return -1.

Insights from the Examples:

• In Example 1, the array has a balance around the middle, where the left sum equals the right sum at index 3. This confirms our pivot index approach.
• Example 2 demonstrates a situation where no index could serve as the pivot, leading to a return value of -1. This helps us understand and account for cases where balance is not attainable between left and right sums.
• Example 3 addresses the edge case where the pivot index could be at the very start of the array. This guides the implementation to correctly handle and check the sums even when one of the sides effectively holds no elements.

Solutions

class Solution {
    public int findPivotIndex(int[] elements) {
        int totalSum = 0, leftSideSum = 0;
        for (int elem: elements) totalSum += elem;
        for (int index = 0; index < elements.length; index++) {
            if (leftSideSum == totalSum - leftSideSum - elements[index]) {
                return index;
            }
            leftSideSum += elements[index];
        }
        return -1;
    }
}