724. Find Pivot Index Easy

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
The two sums are equal.

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

Approach

Input: An integer array nums

Output: Find the leftmost pivot index, which is the index where the sum of all elements to the left equals the sum of all elements to the right

This problem belongs to the 1D Prefix Sum category.

We can first calculate the total sum of the entire array, total. Then, use a variable to keep track of the current number's prefix sum, prefix. The suffix sum can be derived as suffix = total - prefix - nums[i].

Traversing from left to right, as soon as we find a number where Prefix Sum = Suffix Sum, that is the leftmost pivot index, so we return it.

If we finish traversing the array without returning, it means no such index exists, so we return -1.

Implementation

python

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)  # Calculate the total sum of the entire array
        left_sum = 0       # Initialize the left prefix sum to 0

        for i, num in enumerate(nums):
            # If the left prefix sum equals the right prefix sum, return the current index
            # Right prefix sum = total sum - current value - left prefix sum
            if left_sum == total - num - left_sum:
                return i
            left_sum += num  # Update the left prefix sum
        
        return -1  # If no qualifying index is found, return -1

javascript

var pivotIndex = function(nums) {
    // 1. First, calculate the total sum of the entire array
    const total = nums.reduce((acc, cur) => acc + cur, 0);

    // 2. prefix records the sum of elements to the left of the current position
    let prefix = 0;

    for (let i = 0; i < nums.length; i++) {
        // If the sum on the left == the sum on the right, we've found the pivot index
        // Right sum = total sum - left sum - current element
        if (prefix === total - prefix - nums[i]) {
            return i;
        }

        // Update the left sum (adding the current element into it for the next iteration)
        prefix += nums[i];
    }

    // 3. If we finish the traversal and haven't found it, return -1
    return -1;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

724. Find Pivot Index (English)724. 寻找数组的中心下标 (Chinese)