Lesson 9 — Prefix sums: precompute once

~20 minutes · Day 5-6 · prefix sums · Python

Interview arrays often hide the same expensive question: “what is the sum on the left, the right, or inside this range?” If you recompute that sum every time, the code feels simple but burns time. Prefix sums turn repeated adding into one precompute step, then cheap answers.

The invariant

Precompute a running total once, then answer any range or split in O(1).

That's the whole pattern. A prefix sum stores the total up to each position. Once that memory exists, a later question can subtract two stored totals instead of walking the same values again.

What Python gives you

Python gives you the pieces directly: sum to get one total, enumerate to walk values with indices, and a list to store prefix totals. The idea is not Python-specific; Python just keeps the mechanics small.

Find Pivot Index: the slow way first

Find Pivot Index: return the first index where the sum strictly to the left equals the sum strictly to the right.

The direct approach is to try each index, then re-sum both sides:

def pivot_index_slow(nums):
    for i in range(len(nums)):
        if sum(nums[:i]) == sum(nums[i + 1:]):   # re-add both sides
            return i
    return -1

This is O(n²): there are n candidate indices, and each candidate asks Python to add slices of the array again. The slow part is not the comparison; the slow part is forgetting sums you could have carried forward.

Find Pivot Index: the prefix way

Keep one running left sum. The full total is known from the start. At index i with value x, the right sum is everything except the left side and x itself:

For a pivot check, the right side is found by subtracting the known left side and current value from the total.

def pivot_index(nums):
    total = sum(nums)              # all values once
    left = 0                       # sum before current index
    for i, x in enumerate(nums):
        right = total - left - x   # sum after current index
        if left == right:          # split is balanced
            return i
        left += x                  # current joins the left side
    return -1

The check is the invariant in miniature: once total and left are known, the split answer is O(1). The scan only moves forward.

Transfer: same pattern, new question

Range Sum Query - Immutable: build an object that answers sumRange(left, right) many times for the same fixed array.

Before opening the reveal: what should be precomputed, and how can one range be answered by subtracting two stored totals?

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]                         # sum before index 0
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

What the trade buys you

The trade is simple: spend a little memory, stop doing the same addition again.

Practice — answer before you scroll past

prefix = [0]
for x in nums:
    prefix.append(x)

Your move (tonight)

Solve these on LeetCode, in order, logging each in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Find Pivot Index — first predict the brute force, then write the one-pass prefix version from memory.
2. Range Sum Query - Immutable — predict the prefix array shape before writing the class.

For the encode step, write the invariant at the top of this page in your own words. That line is what revision days will test.