#724

Easy

LeetCode Problem Workspace

Find Pivot Index

Find the pivot index in an array where the sums of elements on both sides are equal using array and prefix sum techniques.

array prefix sum

Problem Statement

Given an integer array, identify the pivot index where the sum of all numbers strictly to the left equals the sum of all numbers strictly to the right. If multiple indices satisfy this condition, return the leftmost one.

For the edges, the sum of numbers outside the array bounds is treated as 0. If no such index exists, return -1. The array can contain negative numbers, and the solution must handle arrays up to length 10,000.

Examples

Example 1

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

Output: 3

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

There is no index that satisfies the conditions in the problem statement.

Example 3

Input: nums = [2,1,-1]

Output: 0

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

Solution Approach

Compute Total and Track Left Sum

Calculate the total sum of the array. Iterate through each index, maintaining a left sum that starts at 0. At each step, if left sum equals total minus left sum minus current element, return that index.

Use Prefix Sum Array

Build a prefix sum array where prefix[i] is the sum of elements up to index i-1. For each index, left sum is prefix[i], right sum is total minus prefix[i+1]. Check equality to identify pivot index.

Optimize for Single Pass

Avoid extra space by updating left sum during iteration and comparing with total minus left sum minus current element. This reduces space to O(1) while maintaining O(n) time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single pass through the array or O(n) to build prefix sums. Space complexity is O(1) for single pass or O(n) for storing prefix sums.

What Interviewers Usually Probe

Expect clarification on edge handling when pivot is at the start or end of the array.
Look for discussion on negative numbers affecting left-right sum comparison.
Observe if candidate optimizes space by avoiding a full prefix sum array.

Common Pitfalls or Variants

Common pitfalls

Confusing left sum and right sum indices, especially at array boundaries.
Not handling cases where no pivot exists and returning incorrect indices.
Using extra space unnecessarily when a single pass can suffice.

Follow-up variants

Return all indices where left sum equals right sum instead of only the leftmost.
Find pivot index for a circular array where sums wrap around the end.
Determine pivot index with additional constraints, e.g., only even elements counted.

FAQ

What is the pivot index in the context of this problem?

The pivot index is the position where the sum of all elements to the left equals the sum of all elements to the right.

Can the array contain negative numbers?

Yes, the array can include negative values, and the pivot calculation must account for them accurately.

What if no pivot index exists?

If no index satisfies the left-right sum equality, the function should return -1.

How does the prefix sum pattern help?

Prefix sums allow constant-time calculation of left and right sums at each index, optimizing the search for the pivot index.

Is there a space-efficient way to find the pivot index?

Yes, by maintaining a running left sum and comparing it to total minus left sum minus current element, space can be reduced to O(1).

terminal

Solution

Solution 1: Prefix Sum

We define a variable $left$ to represent the sum of elements to the left of index $i$ in the array $\textit{nums}$, and a variable $right$ to represent the sum of elements to the right of index $i$ in the array $\textit{nums}$. Initially, $left = 0$, $right = \sum_{i = 0}^{n - 1} nums[i]$.

1

2

3

4

5

6

7

8

9

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left, right = 0, sum(nums)
        for i, x in enumerate(nums):
            right -= x
            if left == right:
                return i
            left += x
        return -1

Continue Practicing

#731 my calendar ii #713 subarray product less than k #689 maximum sum of 3 non overlapping subarrays