Suppose you’re given an array once and then asked thousands of questions about it: what’s the total from index 2 to index 5? From 0 to 7? Adding up each range from scratch costs O(n) per question. A prefix sum array costs one O(n) pass up front and answers every later question with a single subtraction.
That’s the whole idea, and it’s simple enough that the interesting parts are the details: an indexing convention that removes edge cases, and a pairing with a hash map that solves a problem sliding windows can’t.
Pick the convention with a zero in front
Define prefix[i] as the sum of the first i elements. The array has n + 1 entries, and prefix[0] is the sum of no elements, which is 0. The sum of the inclusive range l..r is then everything up to r minus everything before l:
def build_prefix(nums):
prefix = [0] * (len(nums) + 1) # prefix[i] = sum of the first i elements
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
return prefix
def range_sum(prefix, l, r):
"""Sum of nums[l..r], both ends inclusive."""
return prefix[r + 1] - prefix[l]For nums = [3, -1, 4, 1, 5, 9, 2, 6]:
prefix = [0, 3, 2, 6, 7, 12, 21, 23, 29]
sum(nums[0..0]) = 3 check: 3
sum(nums[2..5]) = 19 check: 19
sum(nums[0..7]) = 29 check: 29
sum(nums[7..7]) = 6 check: 6Take 2..5: prefix[6] is 21 (the first six elements) and prefix[2] is 2 (the first two), and 21 - 2 = 19, which is 4 + 1 + 5 + 9. In Python, itertools.accumulate(nums, initial=0) builds the same array in one line.
The alternative convention, where running[i] includes nums[i], has no slot for “nothing yet”, so a range starting at index 0 needs its own branch. Forget it, and Python’s negative indexing turns the bug into a quiet wrong answer rather than a crash:
running = list(accumulate(nums)) # running[i] includes nums[i]
def range_sum_inclusive(l, r):
return running[r] - running[l - 1] # l = 0 reads running[-1], the LAST elementinclusive convention, sum(nums[0..2]): -23 expected: 6running[-1] is the total of the whole array, 29, so the result is 6 - 29. In Java or JavaScript the same mistake would throw or return NaN, which is at least loud. The extra zero costs one array slot and removes the entire category of bug, which is why it’s the convention to reach for in an interview.
What the precomputation buys
With n elements and q queries, recomputing each range costs O(n · q) in the worst case. Prefix sums cost O(n) to build and O(1) per query, so O(n + q) overall, with O(n) extra space for the array. On 20,000 random integers and 20,000 random ranges, with Python’s fast built-in sum doing the naive version:
n=20,000, q=20,000: slicing + sum 1744 ms, prefix sums 2.2 msRoughly 800 times faster, and the gap grows with both n and q. The trade-off to mention: prefix sums assume the array doesn’t change. If values are updated between queries, every prefix after the change shifts, and you need a Fenwick tree or segment tree, which handle both updates and queries in O(log n).
Counting subarrays that sum to k
The most common interview use of prefix sums isn’t answering given queries. It’s Subarray Sum Equals K: count the contiguous subarrays whose sum is exactly k.
Rewrite the condition using prefix sums. A subarray ending at position j and starting after position i sums to prefix[j] - prefix[i]. You want that to equal k, so for each j you’re asking: how many earlier prefix sums equal prefix[j] - k? That’s a counting question, and a hash map answers it in O(1):
def subarray_sum(nums, k):
seen = {0: 1} # prefix sum -> how many times it has occurred
running = count = 0
for x in nums:
running += x
count += seen.get(running - k, 0) # earlier prefixes that leave exactly k
seen[running] = seen.get(running, 0) + 1
return countTracing [1, 2, 3] with k = 3:
x= 1 running= 1 looking for -2 count=0 seen={0: 1, 1: 1}
x= 2 running= 3 looking for 0 count=1 seen={0: 1, 1: 1, 3: 1}
x= 3 running= 6 looking for 3 count=2 seen={0: 1, 1: 1, 3: 1, 6: 1}
2At x = 2, the running total is 3, and we look for an earlier prefix of 3 - 3 = 0. The entry {0: 1} represents the empty prefix before the array starts, so this match is the subarray [1, 2]. At x = 3, we look for 3, which was recorded one step earlier, and that match is the subarray [3].
That {0: 1} seed is the same “zero in front” idea from the range-sum convention, and leaving it out is the classic bug. Without it, every subarray that starts at index 0 is missed:
without {0: 1}: 1Other inputs: [1, -1, 0] with k = 0 gives 3, [1, 1, 1] with k = 2 gives 2, and [3, 4, 7, 2, -3, 1, 4, 2] with k = 7 gives 4. A randomised test against the O(n²) double loop, on arrays full of negatives and zeros, agreed on all 2,000 cases.
Why not a sliding window? A window works when growing it always increases the sum and shrinking always decreases it, which requires non-negative numbers. With [1, -1, 0], adding an element can lower the sum, so a window has no safe rule for when to shrink. The prefix sum approach doesn’t care about signs. Time is O(n) and space O(n) for the map. One more detail interviewers check: the lookup happens before recording the current prefix. Reverse the two lines and, when k = 0, every position matches itself as an empty subarray.
Prefix sums in two dimensions
The idea extends to grids. Let P[r][c] be the sum of the rectangle from the top-left corner to just before row r and column c, again with a row and column of zeros in front. Building it and querying it both use inclusion-exclusion: add the two overlapping rectangles, subtract the part counted twice.
def build_2d(grid):
rows, cols = len(grid), len(grid[0])
P = [[0] * (cols + 1) for _ in range(rows + 1)] # P[r][c] = sum of grid[0..r-1][0..c-1]
for r in range(rows):
for c in range(cols):
P[r + 1][c + 1] = grid[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]
return P
def rect_sum(P, r1, c1, r2, c2):
"""Sum of grid[r1..r2][c1..c2], inclusive."""
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]For the grid [[3, 0, 1, 4], [5, 6, 3, 2], [1, 2, 0, 1]], the rectangle from (1, 1) to (2, 2) returns 11 (6 + 3 + 2 + 0), the whole grid returns 28, and the single cell (2, 3) returns 1. A check against direct summation on 500 random grids passed. Building is O(rows · cols); each query is O(1). Image processing uses the same structure under the name “summed-area table”.
Interview practice: product of array except self
Given nums, return an array where answer[i] is the product of every element except nums[i]. You can’t use division, it must run in O(n), and extra space should be O(1) not counting the output array. For [1, 2, 3, 4] the answer is [24, 12, 8, 6].
Answer
The product of everything except nums[i] is (product of everything to the left of i) times (product of everything to the right of i). Those are a prefix product and a suffix product, each with an empty product of 1 at the boundary, the multiplicative version of prefix[0] = 0.
To stay within O(1) extra space, use the output array itself for the prefix products, then sweep from the right keeping the suffix product in a single variable:
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n): # out[i] = product of everything left of i
out[i] = left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1): # multiply in everything right of i
out[i] *= right
right *= nums[i]
return out
print(product_except_self([1, 2, 3, 4]), product_except_self([-1, 1, 0, -3, 3]),
product_except_self([0, 0]))[24, 12, 8, 6] [0, 0, 9, 0, 0] [0, 0]Notice the order inside each loop: store the product so far before multiplying in nums[i], so position i never includes itself. Zeros are where the division shortcut (total product divided by nums[i]) breaks: with one zero, every other position becomes 0 and dividing by it fails, while the zero’s own position needs the product of the rest (9 in the second example). The prefix-suffix approach handles any number of zeros with no special cases. Time is O(n), two passes; extra space is two variables. Run it against the tests on Product of Array Except Self.