Find Pivot Index

Problem

Given an integer array nums, find its pivot index: an index where the sum of all elements strictly to its left equals the sum of all elements strictly to its right. The element at the pivot itself belongs to neither side.

For the leftmost index, the left sum is 0; for the rightmost index, the right sum is 0. Return the leftmost pivot index, or -1 if none exists.

Examples

• nums = [1,7,3,6,5,6] → 3 — left of index 3: 1 + 7 + 3 = 11; right of it: 5 + 6 = 11.
• nums = [1,2,3] → -1 — no index balances (e.g. at index 0: left 0 vs right 5).
• nums = [2,1,-1] → 0 — left of index 0 is empty (0), and right is 1 + (-1) = 0.

Constraints

• 1 <= len(nums) <= 10^4
• -1000 <= nums[i] <= 1000

Recomputing both sums for every candidate index is O(n^2); the intended solution is a single O(n) pass.

Think about it first

TL;DR

Running left sum against a precomputed total — O(n) time, O(1) space.

Approach 1 — Brute force

For every index, sum the elements to its left and the elements to its right with fresh loops (slices), and compare.

from typing import List


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

Complexity: O(n^2) time (each candidate re-sums nearly the whole array), O(n) space for the slices. At n = 10^4 that is ~10^8 additions — the constraints are chosen to make this time out.

Approach 2 — Prefix sum array

The insight: all those repeated sums overlap. Precompute the prefix sums — a classic technique where prefix[i] stores the sum of the first i elements — and every range sum becomes a subtraction: left of i is prefix[i], right of i is prefix[n] - prefix[i + 1].

from typing import List


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

Walkthrough on nums = [1,7,3,6,5,6]:

• prefix = [0, 1, 8, 11, 17, 22, 28].
• i = 0: left 0, right 28 - 1 = 27 — no.
• i = 1: left 1, right 28 - 8 = 20 — no.
• i = 2: left 8, right 28 - 11 = 17 — no.
• i = 3: left 11, right 28 - 17 = 11 — match, return 3.

Complexity: O(n) time, O(n) space for the prefix array.

Approach 3 — Running sum, O(1) space

The insight: you never need the whole prefix array — only the prefix at the current index. Keep one running left, and derive the right side from the fixed total: right = total - left - nums[i].

from typing import List


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:
                return i
            left += x
        return -1

Walkthrough on nums = [2,1,-1] (total = 2):

And on [1,7,3,6,5,6] (total = 28): left runs 0, 1, 8, 11; at i = 3, 28 - 11 - 6 = 11 = left → return 3.

Complexity: O(n) time, O(1) extra space.

Common pitfalls

• Including nums[i] in one of the sides — the pivot element belongs to neither sum. The check is left == total - left - nums[i], not left == total - left.
• Updating left += x before the comparison — that shifts every check by one element and breaks the leftmost-index guarantee.
• Forgetting the edges: index 0 (empty left side) and index n - 1 (empty right side) are legal pivots — example 3 returns 0.
• Assuming positive numbers: with negatives, sums are not monotonic, so binary-search-style shortcuts are invalid; the linear scan is the right tool.

Pattern takeaway

When a problem asks the same range-sum question at many positions, compute the total once and maintain a running prefix — every “sum of a side” becomes O(1) arithmetic. Prefix sums (stored or running) are the standard cure for repeated overlapping sums, and the running-variable form saves the array whenever you only consume prefixes in order.