724. Find Pivot Index

LeetCode Problem Link (opens new window)

Given an integer array nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers on its left is equal to the sum of all the numbers on its right.

If the pivot index is at the left-most position, the left sum is considered to be 0, because there are no elements to the left. The same logic applies for the right-most position.

If there are multiple pivot indexes, return the one closest to the left. If there is no pivot index, return -1.

Example 1:

• Input: nums = [1, 7, 3, 6, 5, 6]
• Output: 3
• Explanation: The pivot index is 3. The sum of numbers on the left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11, and the sum of numbers on the right sum = nums[4] + nums[5] = 5 + 6 = 11, both sums are equal.

Example 2:

• Input: nums = [1, 2, 3]
• Output: -1
• Explanation: There is no index satisfying the pivot index condition.

Example 3:

• Input: nums = [2, 1, -1]
• Output: 0
• Explanation: The pivot index is 0. The sum of numbers on the left sum = 0 (since there are no elements to the left), and the sum of numbers on the right sum = nums[1] + nums[2] = 1 + -1 = 0, both sums are equal.

Approach

This problem is relatively straightforward:

1. Iterate through the array to calculate the total sum.
2. Iterate a second time to calculate the leftSum of the pivot index.
   • Simultaneously, calculate the rightSum of the pivot index using the sum and leftSum.
   • Check if leftSum and rightSum are equal.

Here is the C++ code:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        for (int num : nums) sum += num; // Calculate total sum
        int leftSum = 0;    // Sum of the left part of the pivot index
        int rightSum = 0;   // Sum of the right part of the pivot index
        for (int i = 0; i < nums.size(); i++) {
            leftSum += nums[i];
            rightSum = sum - leftSum + nums[i];
            if (leftSum == rightSum) return i;
        }
        return -1;
    }
};

Versions in Other Languages

Java

class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i]; // Calculate total sum
        }
        int leftSum = 0;
        int rightSum = 0;
        for (int i = 0; i < nums.length; i++) {
            leftSum += nums[i];
            rightSum = sum - leftSum + nums[i]; // leftSum already includes nums[i], subtracted once too much, so add it back
            if (leftSum == rightSum) {
                return i;
            }
        }
        return -1; // Not found
    }
}

Python3

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        numSum = sum(nums) # Calculate total sum
        leftSum = 0
        for i in range(len(nums)):
            if numSum - leftSum - nums[i] == leftSum: # left and right sums are equal
                return i
            leftSum += nums[i]
        return -1

Go

func pivotIndex(nums []int) int {
	sum := 0
	for _, v := range nums {
		sum += v;
	}

	leftSum := 0    // Sum of the left part of the pivot index
	rightSum := 0   // Sum of the right part of the pivot index
	for i := 0; i < len(nums); i++ {
		leftSum += nums[i]
		rightSum = sum - leftSum + nums[i]
		if leftSum == rightSum{
			return i
		}
	}
	return -1
}

JavaScript

var pivotIndex = function(nums) {
    const sum = nums.reduce((a,b) => a + b);// Calculate total sum
    // Sum of the left part of the pivot index, Sum of the right part of the pivot index
    let leftSum = 0, rightSum = 0;
    for(let i = 0; i < nums.length; i++){
        leftSum += nums[i];
        rightSum = sum - leftSum + nums[i]; // leftSum already includes nums[i], subtracted once too much, so add it back
        if(leftSum === rightSum) return i;
    }
    return -1;
};

TypeScript

function pivotIndex(nums: number[]): number {
    const length: number = nums.length;
    const sum: number = nums.reduce((a, b) => a + b);
    let leftSum: number = 0;
    for (let i = 0; i < length; i++) {
        const rightSum: number = sum - leftSum - nums[i];
        if (leftSum === rightSum) return i;
        leftSum += nums[i];
    }
    return -1;
};