Home / Blog / Prefix Sum Interview Pattern Chooser

Prefix Sum Interview Pattern Chooser

Published 2026-10-09 · Luna Interview

Prefix sums turn range questions into constant-time arithmetic—if you pick the right shape. The prefix sum interview pattern chooser is about classification: plain 1D prefixes, prefix + hash map for “sum equals k,” difference arrays for range updates, and 2D prefixes for matrices. Mixing them up costs a full attempt.

The 10-second classification

Ask:

1. Do I need many range sum queries on a static array?
2. Do I need a subarray whose sum equals a target (any length)?
3. Do I apply many range increments, then ask for the final array?
4. Are queries on a matrix sub-rectangle?

Talk track:

“If the array is static and I need sum(l..r) often, I’ll precompute prefix. If I need count of subarrays with sum k, I’ll pair prefix with a frequency map. If I have range updates, I’ll use a difference array.”

Pattern menu

If the window must be contiguous and you optimize length under a constraint with non-negative numbers, sliding window may beat hash-map prefix. Say that tradeoff out loud.

1D prefix template

def build_pref(a):
    n = len(a)
    pref = [0] * (n + 1)
    for i, x in enumerate(a):
        pref[i + 1] = pref[i] + x
    return pref

def range_sum(pref, l, r):  # inclusive l..r
    return pref[r + 1] - pref[l]

Invariant: pref[i] is sum of the first i elements (a[0..i-1]). State the inclusive/exclusive convention once and stick to it.

Talk track:

“sum(l..r) = pref[r+1] - pref[l]. I’ll keep pref length n+1 so empty prefix is zero.”

Subarray sum equals k (prefix + map)

from collections import defaultdict

def subarray_sum(nums, k):
    count = 0
    pref = 0
    seen = defaultdict(int)
    seen[0] = 1  # empty prefix
    for x in nums:
        pref += x
        count += seen[pref - k]
        seen[pref] += 1
    return count

Why it works: if pref[j] - pref[i] = k, then a subarray (i..j-1) sums to k. The map stores how many times each prefix appeared.

Common prompts: count of such subarrays, or existence. Clarify which.

Bugs:

• Forgetting seen[0] = 1
• Updating the map before querying pref - k when you should not (order matters for “at least one index earlier”)
• Assuming positivity so you “could” use two pointers—negatives break window shrink logic

Talk track:

“Negatives allowed, so sliding window isn’t safe. Prefix frequency map stays O(n).”

Difference array (range updates)

def apply_ranges(n, updates):
    diff = [0] * (n + 1)
    for l, r, val in updates:  # inclusive
        diff[l] += val
        diff[r + 1] -= val
    out = [0] * n
    run = 0
    for i in range(n):
        run += diff[i]
        out[i] = run
    return out

Use when you never need intermediate range sums during updates—only the final flattened array (or you rebuild prefix afterward).

2D prefix (submatrix sums)

# pref[i][j] = sum of matrix[0..i)[0..j)
def build_2d(mat):
    m, n = len(mat), len(mat[0])
    pref = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            pref[i + 1][j + 1] = (
                mat[i][j]
                + pref[i][j + 1]
                + pref[i + 1][j]
                - pref[i][j]
            )
    return pref

def rect_sum(pref, r1, c1, r2, c2):  # inclusive
    return (
        pref[r2 + 1][c2 + 1]
        - pref[r1][c2 + 1]
        - pref[r2 + 1][c1]
        + pref[r1][c1]
    )

Narrate inclusion-exclusion: add big rectangle, subtract the two overhangs, add back the double-subtracted corner.

When prefix sum is the wrong chooser

• Need maximum subarray (Kadane) without range queries—don’t overbuild prefix
• Need shortest window with sum ≥ S on non-negative array → sliding window
• Need order statistics in range → segment tree / fenwick (mention only if leveled)
• Updates and queries mixed heavily online → fenwick/segment tree territory; say so if the constraints demand it

First five minutes

1. Static range sum vs subarray-equals-k vs range updates vs 2D
2. Fix inclusive index convention on the pad
3. Write pref[0]=0 (or seen[0]=1)
4. Dry-run a tiny array by hand: [1,2,3], query sum(0,1) and sum equals 3
5. Mention O(n) build / O(1) query (or O(n) for hash-map pass)

Soft practice note

Prefix mistakes are usually convention mistakes under stress—off-by-one on r+1, forgotten seen[0]. If you want a calm loop to rehearse the chooser out loud before live rounds, Luna Interview is built for structured practice and composure, not for anything that violates interview rules.

Day-of checklist

• [ ] Named which prefix variant
• [ ] Inclusive bounds written once
• [ ] pref length n+1 or equivalent
• [ ] For sum=k: seen[0]=1, query before (or carefully after) update
• [ ] Negatives → no naive window
• [ ] 2D: four-corner inclusion-exclusion

Choose the prefix shape first; the arithmetic is easy once the invariant matches the question.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.