DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Find Pivot Index

easyPrefix sum

Problem statement

Given an integer array nums, find an index i where the sum of all elements to the left of i equals the sum of all elements to the right of i. The element at i itself belongs to neither side. An empty side sums to 0.

Return the smallest such index, or -1 if none exists. The numbers may be negative.

Examples

Example 1

Input: nums = [2, 4, 1, 6]

Output: 2

Explanation: Left of index 2: 2 + 4 = 6. Right of index 2: 6.

Example 2

Input: nums = [1, 2, 3]

Output: -1

Explanation: The left/right pairs are 0/5, 1/3 and 3/0. None are equal.

Hints

Approach

Compute the total once. Then scan left to right with a running left sum. At index i, the right side is total - left - nums[i], so the test is one comparison.

  1. total = sum(nums), left = 0.
  2. For each i: if left == total - left - nums[i], return i. Otherwise add nums[i] to left.
  3. Return -1.

Check before adding nums[i] to left, because the pivot element belongs to neither side.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def pivotIndex(self, nums: list[int]) -> int:
total = sum(nums)
left = 0
for i, x in enumerate(nums):
if left == total - left - x: # right side = total - left - x
return i
left += x
return -1

Follow-up questions

  • Return every pivot index instead of the first one.
  • Find the index that makes the two sides as close as possible when no exact pivot exists.

Frequently asked questions

Yes. At index 0 the left side is empty and sums to 0, so it is a pivot when everything after it sums to 0. In [5] the answer is 0, since both sides are empty.

No, because the numbers can be negative. Sums don't grow steadily in one direction, so moving the "smaller side" pointer can skip the real pivot. The total-minus-left formula has no such problem.

The idea of "total minus what I've seen so far" is how you split work evenly, for example choosing where to cut a list of shard sizes so both halves hold the same amount of data, without re-summing each side for every candidate cut.