Prefix Sums

No. 14 · SVG · Running tallyrange sums · subarray sum equals k · prefix and suffix

Drag across the tally. Click it, then use ← → to step and Space to play.

Precompute running totals once, so any range sum is a single subtraction: the total up to R, minus the total before L. One O(n) pass, then every query is O(1). Add a hash map of the prefix sums seen so far and you can also count subarrays with a given sum: a subarray ending here sums to k exactly when some earlier prefix equals (current prefix − k).

FIG. 14 · The array is the top row. The prefix row sits half a slot to the left, so prefix[i] lines up with the gap between nums[i − 1] and nums[i]: it is the total of everything to its left. A range L..R is framed in red, with the two brackets above it showing the prefix up to R and the prefix before L; the range is their difference. The running values are listed on the right.

Step 1 / 1
READY
Slides
Extra space
Window
Result
CodePrefixSum.__init__
class PrefixSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

Examples

Prefix sum · LeetCode 724

nums = [1, 7, 3, 6, 5, 6]. Find i where the sum to its left equals the sum to its right. Keep the prefix (left) sum; the right side is total − left − nums[i]. Answer: 3 (1 + 7 + 3 = 11 = 5 + 6).

O(n) timeO(1) spaceone sum, one pass
Prefix × suffix · LeetCode 238

nums = [1, 2, 3, 4], no division. The answer at i is the product of everything left of i times everything right of i: a prefix product on the way forward, a suffix product on the way back. Answer: [24, 12, 8, 6].

O(n) timeO(1) extra spacetwo passes; the output array doesn't count

Time and space

OperationTimeSpaceWhy
Build the prefix rowO(n)O(n)One addition per element; n + 1 numbers stored.
Each range queryO(1)—prefix[R + 1] − prefix[L]. Summing with a loop would be O(R − L + 1) per query.
Count subarrays summing to kO(n)O(n)One pass with a dict of prefix counts, instead of O(n²) subarrays.

Why the leading 0?

prefix[0] = 0 is the sum of nothing. It lets range_sum(0, R) be prefix[R + 1] − prefix[0] with no special case, and in subarray_sum, count = {0: 1} is the same idea: it lets a subarray that starts at index 0 be found.

Prefix sums vs sliding window

"Subarray sum equals k" looks like a window problem, but a window only works when growing it always increases the sum (all positive numbers). With negatives, shrinking can make the sum go up, and the window doesn't know which way to move. The prefix-sum map doesn't care about signs.

Trigger words: when the problem wants prefix sums

Range queries

  • sum of range L to R
  • many queries

Build once in O(n), answer each in O(1).

Prefix + hash map

  • subarray sum equals k
  • count subarrays

Look up cur − k among the prefixes seen so far.

Template

class PrefixSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def range_sum(self, L, R):     # sum of nums[L..R]
        return self.prefix[R + 1] - self.prefix[L]

def subarray_sum(nums, k):         # count subarrays summing to k
    count = {0: 1}
    cur = res = 0
    for x in nums:
        cur += x
        res += count.get(cur - k, 0)
        count[cur] = count.get(cur, 0) + 1
    return res