{x}
blog image

Find Pivot Index

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:

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

 

Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/

724. Find Pivot Index

Problem Description

Given an array of integers nums, find the pivot index, which 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 no such index exists, return -1.

Approach: Prefix Sum

The most efficient approach to solve this problem is using the prefix sum technique. This avoids redundant calculations by pre-computing cumulative sums.

  1. Calculate the total sum: First, calculate the total sum of all elements in the nums array.

  2. Iterate and compare: Iterate through the array. For each element at index i:

    • Calculate the leftSum (sum of elements to the left of i). This is simply the prefix sum up to i-1.
    • Calculate the rightSum (sum of elements to the right of i). This is the totalSum minus the leftSum minus the element at index i itself.
    • If leftSum equals rightSum, return i.

  3. Return -1: If the loop completes without finding a pivot index, return -1.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the array. We iterate through the array once to calculate the prefix sum and once more to find the pivot index.
  • Space Complexity: O(1). We use only a few variables to store sums and the index; the space used is constant regardless of the input size.

Code Implementation

Here's the code implementation in several languages:

Python

def pivotIndex(nums):
    total_sum = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        right_sum = total_sum - left_sum - num
        if left_sum == right_sum:
            return i
        left_sum += num
    return -1

Java

class Solution {
    public int pivotIndex(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            int rightSum = totalSum - leftSum - nums[i];
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}

C++

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        int leftSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            int rightSum = totalSum - leftSum - nums[i];
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
};

JavaScript

var pivotIndex = function(nums) {
    const totalSum = nums.reduce((a, b) => a + b, 0);
    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;
};

Go

func pivotIndex(nums []int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    leftSum := 0
    for i, num := range nums {
        rightSum := totalSum - leftSum - num
        if leftSum == rightSum {
            return i
        }
        leftSum += num
    }
    return -1
}

These code examples all follow the same prefix sum approach, providing an efficient solution to the problem. Remember to handle edge cases (empty arrays) appropriately if needed, though this solution implicitly handles them by returning -1 if no pivot is found.