Description

Given an array of integers nums, calculate the pivot index of this 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 also applies to the right edge of the array. Return the leftmost pivot index. If no such index exists, return -1.

Example 1:

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

Example 2:

1Input: nums = [1,2,3]
2Output: -1
3Explanation:
4There is no index that satisfies the conditions in the problem statement.

Example 3:

1Input: nums = [2,1,-1]
2Output: 0
3Explanation:
4The pivot index is 0.
5Left sum = 0 (no elements to the left of index 0)
6Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints:

  • 1 <= nums.length <= 10^4
  • -1000 <= nums[i] <= 1000

Solution

In this case, we need to find sum of all values on the left and sum of all values on the right. At any index position, if we knew the sum of all elements of input array nums, then the rightSum will be equal to sum - leftSum - nums[i] at index position i. Here, leftSum is sum of all elements from 0 to i-1 index position. Based on this, if we find a scenario where leftSum == sum - leftSum - nums[i] then that index is what will be pivot index based on the definition of pivot index. Again, we have to start looking from the left hand side to find the first left most pivot index.

1Find sum of all elements and store in sum variable
2leftSum = 0
3for i = 0; i < nums.length; i++
4    if leftSum == sum - leftSum - nums[i]
5        return i
6    leftSum += nums[i]
7return -1

 1class Solution {
 2    public int pivotIndex(int[] nums) {
 3        int sum = 0;
 4        for (int i: nums) {
 5            sum += i;
 6        }
 7        int leftSum = 0;
 8        for (int i = 0; i < nums.length; i++) {
 9            if (leftSum == sum - leftSum - nums[i])
10                return i;
11            leftSum += nums[i];
12        }
13        return -1;
14    }
15}