How do you solve Find Pivot Index?

Initialize left_sum to 0 and right_sum to the total sum of the array. Iterate through the array, decrementing right_sum by the current element and checking if left_sum equals right_sum. If they are equal, return the current index. Otherwise, add the current element to left_sum and continue. If no pivot index is found, return -1.

What pattern does Find Pivot Index use?

The Pattern: Prefix Sum The Heuristic: When a problem requires comparing sums of subarrays repeatedly, precompute the total sum and maintain a running prefix sum to enable constant-time calculation of complementary sums, reducing nested loops to a single pass.

Find Pivot Index — Prefix Sum

Q: What is the time complexity of Find Pivot Index?

O(n). The algorithm computes the total sum once and then iterates through the array once, performing constant-time operations per element.

Problem

Given an integer array nums, return the pivot index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, return -1.

1 ≤ nums.length ≤ 10⁴
−1000 ≤ nums[i] ≤ 1000

Example

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

Output: 3

The pivot index is 3 because the sum of elements to the left (1 + 7 + 3 = 11) equals the sum of elements to the right (5 + 6 = 11). The algorithm starts by calculating the total sum of the array (28). It then iterates through the array, maintaining a running left sum. At index 0, left sum is 0 and right sum is 28 - 1 = 27, which are not equal. At index 1, left sum is 1 and right sum is 27 - 7 = 20, still not equal. This continues until index 3, where left sum is 11 and right sum is 11, satisfying the condition and returning 3.

Approach

Straightforward Solution

A brute-force approach would compute the sum of elements to the left and right of every index separately, resulting in O(n^2) time complexity, which is inefficient for large arrays.

Core Observation

The pivot index is defined by the equality of the sum of elements on its left and right. The total sum of the array can be used to compute the right sum at any index by subtracting the left sum and the current element.

Path to Optimal

By precomputing the total sum of the array, the right sum at any index can be derived by subtracting the left sum and the current element from the total sum. This allows checking the pivot condition in a single pass with O(n) time complexity.

Optimal Approach

Preview

Initialize left_sum to 0 and right_sum to the total sum of the array. Iterate through the array, decrementing right_sum by the current element and checking if left_sum equals right_sum…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm computes the total sum once and then iterates through the array once, performing constant-time operations per element.

Space

O(1)

Only a few integer variables are used to track sums and indices, with no additional data structures proportional to input size.

Solution

Python

1class Solution:
  def pivotIndex(self, nums: List[int]) -> int:
      left_sum = 0
      right_sum = sum(nums)
5
      for index, val in enumerate(nums):
          right_sum -= val
          if left_sum == right_sum:
              return index
          left_sum += val
11
      return -1

Step-by-Step Solution

1

Initialize Left and Right Sums for Pivot Detection

3left_sum = 0
4right_sum = sum(nums)

Objective

To set up the initial sums needed to compare left and right partitions at each index.

Key Insight

Calculating the total sum upfront allows the algorithm to derive the right sum dynamically by subtracting the current element and the accumulated left sum. Starting left_sum at zero reflects that no elements are to the left of the first index.

Interview Quick-Check

Core Logic

Precompute total sum to enable O(1) calculation of right sum at each index by subtracting left_sum and current element.

State & Boundaries

Initialize left_sum to 0 before iteration to represent the sum of elements left of the first index.

2

Iterate Through Array to Identify Pivot Index

To traverse the array, update sums, and check for the pivot condition at each index.

3

Return -1 When No Pivot Index Exists

To signal that no index satisfies the pivot condition after full traversal.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 7 Critical

right_sum -= val

Subtract the current element from right_sum to exclude it from the right partition.

This update ensures right_sum accurately reflects the sum of elements strictly to the right of the current index, which is essential for correct pivot comparison.

Line 8 Critical

if left_sum == right_sum:

Check if left_sum equals right_sum to identify the pivot index.

This equality check is the core condition defining the pivot index; detecting this condition immediately allows early return for efficiency.

Line 4 Critical

right_sum = sum(nums)

Calculate the total sum of the array to represent the initial right sum.

Precomputing the total sum allows the algorithm to derive the right sum at any index by subtracting left_sum and the current element, enabling O(1) right sum calculation per iteration.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does subtracting the current element from the total sum give the right sum at the current index?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find Pivot Index from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find Pivot Index drill

or drill a free problem

1	`class Solution:`
2	`def pivotIndex(self, nums: List[int]) -> int:`
3	`left_sum = 0`
4	`right_sum = sum(nums)`
5
6	`for index, val in enumerate(nums):`
7	`right_sum -= val`
8	`if left_sum == right_sum:`
9	`return index`
10	`left_sum += val`
11
12	`return -1`