Find Pivot Index

Difficulty: Easy | Acceptance: 62.60% | Paid: No Topics: Array, Prefix Sum

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 right of the index.

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.

• Examples
• Constraints
• Brute Force
• Prefix Sum

Examples

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)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints

1 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000

Brute Force

Intuition For each index in the array, we can explicitly calculate the sum of elements to its left and the sum of elements to its right by iterating through the relevant portions of the array.

Steps

• Iterate through each index i from 0 to n-1.
• Calculate left_sum by iterating from 0 to i-1.
• Calculate right_sum by iterating from i+1 to n-1.
• If left_sum equals right_sum, return i.
• If the loop finishes without finding a pivot, return -1.

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            left_sum = sum(nums[:i])
            right_sum = sum(nums[i+1:])
            if left_sum == right_sum:
                return i
        return -1

Complexity

• Time: O(n²) - For each index, we traverse the array to calculate sums.
• Space: O(1) - We only use a few variables for summation.
• Notes: This approach is simple but inefficient for large arrays.

Prefix Sum

Intuition We can optimize the solution by pre-calculating the total sum of the array. As we iterate through the array, we maintain a running left_sum. The right_sum for the current index can be derived by subtracting the left_sum and the current element from the total_sum.

Steps

• Calculate the total_sum of all elements in nums.
• Initialize left_sum to 0.
• Iterate through the array:
  • Check if left_sum equals total_sum - left_sum - nums[i].
  • If true, return i.
  • Add nums[i] to left_sum.
• If the loop completes, return -1.

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0
        for i in range(len(nums)):
            if left_sum == total_sum - left_sum - nums[i]:
                return i
            left_sum += nums[i]
        return -1

Complexity

• Time: O(n) - We pass through the array twice (once for total sum, once for the pivot check).
• Space: O(1) - We only use variables to store sums.
• Notes: This is the optimal solution for this problem.