deepSWE.io

Find Pivot Index

Prefix SumArray

20 min

Problem Statement

Given an array of integers nums, find the pivot index. This is the index where the sum of all numbers to the left is equal to the sum of all numbers to the right.

If no such index exists, return -1. If there are multiple pivot indexes, return the left-most one.

Example

Example 1:

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

Output: 3

Explanation: The sum of the numbers to the left of index 3 (1 + 7 + 3 = 11) is equal to the sum of numbers to the right (5 + 6 = 11).

Solution

The core idea is to iterate through the array while keeping track of the sum of elements to the left (`leftSum`). The sum of elements to the right (`rightSum`) can be efficiently calculated by first computing the `totalSum` of the array.

For each index `i`, the `rightSum` is simply `totalSum - leftSum - nums[i]`. We check if `leftSum` equals `rightSum`. If it does, we've found the pivot.

Algorithm Steps

Calculate the `totalSum` of the entire array.
Initialize `leftSum = 0`.
Iterate through the array from left to right.
At each index `i`, check if `leftSum == totalSum - leftSum - nums[i]`.
If they are equal, `i` is the pivot index.
After the check, update `leftSum` by adding `nums[i]`.
If the loop completes, no pivot was found, so return -1.

Find Pivot Index

Prefix Sum Approach

Progress1 / 5

Start. Total Sum is calculated.

Array

Left Sum

Right Sum

Find Pivot Index


class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0
        for i, num in enumerate(nums):
            # right_sum = total_sum - left_sum - current_num
            if left_sum == total_sum - left_sum - num:
                return i
            left_sum += num
        return -1