Skip to main content
DSA patterns

Find Pivot Index

easyPrefix sumAmazonAccentureDell

Problem statement

You're given an array of integers nums. The pivot index is a position where the sum of everything strictly to its left equals the sum of everything strictly to its right. If the position sits at either edge of the array, the missing side counts as a sum of 0.

Return the leftmost pivot index. If no such index exists, return -1.

Examples

Example 1

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

Output: 3

Explanation: At index 3, the left side is 1 + 7 + 3 = 11 and the right

Example 2

Input: nums = [1,2,3]

Output: -1

Explanation: No index makes the left and right sums equal, so there is no

Example 3

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

Output: 0

Explanation: At index 0, the left side has nothing to add, so it's 0.

Hints

Hint 1: At any index, the left sum, the value at that index, and the right sum always add up to the total sum of the whole array.

Approach

Optimal: Total sum minus a running left sum

Intuition

The left sum, the value at the current index, and the right sum always add up to the array's total — that never changes no matter where you are. So once you know the total up front, you can get the right sum for free at every index with a single subtraction: rightSum = total - leftSum - nums[i]. That removes the need to ever scan the right side directly, which is what turns O(n²) into O(n).

Steps

  1. Compute total, the sum of the whole array.
  2. Start with leftSum = 0.
  3. For each index i from 0 to n - 1:
    • Compute rightSum = total - leftSum - nums[i].
    • If leftSum == rightSum, return i.
    • Otherwise, add nums[i] to leftSum and move to the next index.
  4. If the loop finishes with no match, return -1.

Dry run

nums = [1, 7, 3, 6, 5, 6], total = 1+7+3+6+5+6 = 28

i nums[i] leftSum before rightSum = total − leftSum − nums[i] equal? leftSum after
0 1 0 28 − 0 − 1 = 27 no 1
1 7 1 28 − 1 − 7 = 20 no 8
2 3 8 28 − 8 − 3 = 17 no 11
3 6 11 28 − 11 − 6 = 11 yes → return 3 —

Every rightSum here is computed with one subtraction, using the running leftSum — the right side of the array is never scanned directly.

Edge cases: for nums = [1, 2, 3] (Example 2), no index ever makes leftSum equal rightSum, so the loop finishes and the function correctly returns -1. For nums = [2, 1, -1] (Example 3), leftSum starts at 0 and rightSum at index 0 is 2 - 0 - 2 = 0 — they already match, so the answer is 0 even though the array contains a negative number; the subtraction logic doesn't care about sign.

Complexity

Time O(n) - one pass to add up the total, then one more pass where each step does a constant amount of work: no more re-scanning the right side at every index.

Space O(1) - extra — just the total and a running left sum.

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


if __name__ == "__main__":
    print(Solution().pivotIndex([1, 7, 3, 6, 5, 6]))   # 3
    print(Solution().pivotIndex([1, 2, 3]))            # -1
    print(Solution().pivotIndex([2, 1, -1]))           # 0
RecapThe whole problem in a few lines, for the night before
  • Spot it: an index where the sum on the left equals the sum on the right
  • Idea: compute the total once; walk the array and check left sum == total - left sum - nums[i]
  • Cost: O(n) time, O(1) space
  • Trap: the element at the pivot belongs to neither side, and an empty side counts as 0

Interview follow-ups

  • Return every pivot index, not just the leftmost.

    Don't return as soon as one match is found — append the index to a results list instead, and keep going through the same single pass. The time complexity stays O(n); only the amount of output can grow.

  • nums arrives as a stream and can only be read once. How would this change?

    The trick needs the whole array's total before it can check even the first index, so a true single read isn't quite enough on its own. If a second pass over the same data is allowed, do this in two sweeps instead of one: one pass to compute total, and a second pass to find the pivot exactly as before — still O(n) total, just split across two reads.

  • nums can change over time, and you need the pivot index to stay current. What changes?

    Recomputing everything from scratch after every update costs O(n) each time. A Fenwick tree (binary indexed tree) supports both "update one value" and "sum of a prefix" in O(log n) each, so you can still use the same total-minus-leftSum trick, just backed by a structure that keeps prefix sums cheap to maintain as nums changes.

Frequently asked questions

Because leftSum + nums[i] + rightSum always equals the array's total — those three pieces split the whole array with nothing left over and nothing double-counted. Once you know any two of the three, the last one is free: just subtract. That's why the right side never needs to be scanned on its own.

Because the loop checks indices in increasing order and returns the moment it finds a match. The very first index that satisfies the condition is necessarily the leftmost one, so there's no need to check the rest of the array once a match is found.

Picture nums as per-minute request counts across a window of time. A pivot index is the minute that splits the earlier traffic and the later traffic into two equal totals — a natural way to find a balance point, similar to splitting a batch job's workload as evenly as possible across two halves.

No — sums and equality checks don't care whether the numbers are positive or negative. Example 3, [2, 1, -1], shows this directly: the pivot at index 0 works out because 1 + (-1) happens to equal 0, exactly like an empty side would.