Prefix Sum Problems Leave the Same Clues. Learn to Read Them.

You see an array problem. The brute force is O(n²). You know there's a better answer somewhere. And yet you stare. Then you write the nested loops anyway, just to feel something.

Prefix sum problems are one of those patterns where the template is almost insultingly simple. Build a cumulative array, do a lookup, done. The hard part is never the code. It's recognizing, from a problem statement that never says "prefix sum," that this is where you should be.

One Formula, Every Subarray Sum

A prefix array stores running totals. prefix[i] holds the sum of every element from index 0 up to index i-1. Any subarray sum nums[l..r] collapses to a single subtraction.

nums    = [2, -1, 3, 4, -2]
prefix  = [0,  2,  1, 4, 8,  6]
#           ^   ^   ^  ^  ^   ^
#           0   1   2  3  4   5  (prefix index)

The formula: sum(l, r) = prefix[r+1] - prefix[l]

The extra zero at the front is not decoration. It makes the formula uniform for subarrays that start at index 0, so you never need an if l == 0 special case.

Build the array once in O(n), answer every subsequent range query in O(1). Two queries on the same static array and the trade is already worth it.

def build_prefix(nums: list[int]) -> list[int]:
    prefix = [0] * (len(nums) + 1)
    for i, num in enumerate(nums):
        prefix[i + 1] = prefix[i] + num
    return prefix

def range_sum(prefix: list[int], l: int, r: int) -> int:
    return prefix[r + 1] - prefix[l]

Three Clues That Mark Prefix Sum Problems

Problems that need prefix sum never announce it. They describe a shape of computation. No problem has ever said "hint: consider a prefix array." That would be too helpful. Instead they give you these.

Clue 1: Multiple range queries on a static array. "You will receive q requests, each of the form [l, r], return the sum of nums[l..r]." Brute force is O(n) per query, O(nq) total. Prefix sum makes it O(n + q). LeetCode 303 says this explicitly. In practice the phrasing is subtler, but the shape is the same: repeated lookups on data that doesn't change.

Clue 2: Count subarrays whose sum satisfies a condition. "Sum equals k," "sum divisible by k," "equal number of 0s and 1s," "longest subarray with sum 0." Any time "count" appears with "subarray" and some aggregate condition, you're looking at the hashmap variant, covered below.

Clue 3: Sum of elements in a rectangular region. The 2D extension. Build a 2D prefix table in O(mn), answer each rectangle query in O(1) via inclusion-exclusion.

Spot any of these shapes and reach for prefix sum before sliding window, before two pointers, before anything else.

Sliding Window Fails on Negatives

When you see "subarray sum equals k," the first instinct is sliding window. Two pointers, expand right, shrink left when the sum exceeds k. O(n), right?

Wrong. Sliding window requires the window sum to be monotone: shrinking the left boundary must decrease the sum. That holds when all elements are positive. The moment negatives appear, the invariant breaks.

Consider nums = [1, -1, 1, 2, -1], target k = 2. When the window sum hits 3, you shrink. But shrinking might discard the -1 that would have brought you to 2 later. The window is no longer meaningful.

The constraint block is the tell. "nums[i] can be negative," or no range restriction at all, means sliding window fails. You need prefix sum with a hashmap.

The O(n²) solution be like. It compiles. Don't touch it.

Count Subarrays with a Target Sum

The core rearrangement: sum(l+1, r) = k means prefix[r] - prefix[l] = k, which means prefix[l] = prefix[r] - k. Scan left to right, accumulating a running sum. At each position, ask: have I seen a prefix value equal to currentSum - k? Every prior index with that value starts a valid subarray ending here.

def subarray_sum(nums: list[int], k: int) -> int:
    seen = {0: 1}  # prefix_sum -> count of times seen
    current = 0
    count = 0
    for num in nums:
        current += num
        count += seen.get(current - k, 0)  # check BEFORE inserting
        seen[current] = seen.get(current, 0) + 1
    return count

The {0: 1} initialization is not a trick. It handles subarrays that start at index 0. Without it, any valid subarray from the beginning of the array goes uncounted. Test on [3] with k = 3. If you get 0, the base case is missing. This bug has haunted LeetCode 560 submissions since the problem was added. It will haunt yours too if you skip it.

The modulo variant (LeetCode 974) runs the same skeleton. If prefix[r] % k == prefix[l] % k, then the subarray between them is divisible by k. Store remainders instead of raw sums.

One transformation worth memorizing: subarrays with equal counts of 0s and 1s. Remap 0 → -1, then find subarrays with sum 0. Equal counts become sum-to-zero, and the template handles it directly.

When Prefix Sum Breaks Down

The technique requires the operation to have an inverse. Subtraction reverses addition. XOR is its own inverse (a XOR a = 0). Product prefix technically works, though integer overflow makes it messy in practice.

Range minimum has no inverse. min(0, r) - min(0, l-1) is meaningless. You cannot recover the minimum of a subrange from two prefix minimums. The same is true for maximum, GCD, and any operation that discards information as it accumulates.

This is the line between prefix sum and sparse tables or segment trees. Inverse operation available: use prefix. No inverse: you need a structure that stores intermediate results across the range, not just from the origin.

Flip It: Range Updates in O(1)

Prefix sum turns O(n) preprocessing into O(1) queries. Its exact mirror solves the inverse problem: O(1) range updates with O(n) final reconstruction.

Suppose you need to add val to every element in nums[l..r], across many such updates. Applying each update naively is O(n) per operation. Instead, maintain a difference array: diff[l] += val and diff[r+1] -= val. After all updates, take the prefix sum of diff to get the final array.

def apply_range_updates(n: int, updates: list[tuple]) -> list[int]:
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l] += val
        diff[r + 1] -= val
    result = []
    running = 0
    for d in diff[:n]:
        running += d
        result.append(running)
    return result

LeetCode 1094 (Car Pooling) and 1109 (Corporate Flight Bookings) are the canonical examples. The signal: many overlapping range operations, then read the final state rather than answer individual queries.

Three Bugs That Kill Correct Solutions

You will write a solution that looks right and produces wrong answers. One of these three is responsible.

Update order in the hashmap variant. Check seen.get(current - k, 0) before inserting current into seen. Insert first and you allow the current element to match itself, counting a zero-length subarray as valid. The code compiles fine. The tests fail. You lose 20 minutes.

Missing the {0: 1} base case. Worth its own bullet because it's the most common wrong answer on LeetCode 560. Test [3] with k = 3. If you get 0, you know what to fix. Do this test before submitting. Do it now, in fact.

Negative modulo in Java and C++. Python's % always returns non-negative: -7 % 3 == 2. Java and C++ return negative remainders: -7 % 3 == -1. Store remainders as hashmap keys in either language without normalizing and you'll end up with both -1 and 2 as separate keys for the same bucket. The fix is explicit normalization: ((r % k) + k) % k. This one bites people who switch languages mid-prep and assume consistent behavior.

There's also the off-by-one in the range formula. sum(l, r) is prefix[r+1] - prefix[l], not prefix[r] - prefix[l-1]. The leading-zero convention keeps this clean. Pick it and stay consistent.

Quick Reference

Basic prefix sum: multiple range sum queries on a static array.

Prefix sum + hashmap: count subarrays with sum k (especially with negatives); longest/shortest subarray with property X; sum divisible by k (modulo variant); equal 0s and 1s in a binary array (remap 0 to -1 first).

2D prefix sum: sum of elements in a rectangle with multiple queries.

Difference array: many range updates, then read the final state.

The invariant: the operation must have an inverse. Subtraction for addition. XOR for XOR. Nothing for min, max, or GCD.

The three bugs: check before insert; {0: 1} initialization; normalize negative modulo in Java/C++.

---

Naming the pattern under pressure, mid-interview, is a different skill than implementing the template. SpaceComplexity runs voice-based mock interviews where you practice explaining why you're reaching for prefix sum instead of sliding window, and catching your own bugs out loud. That's the part LeetCode can't train.

---

Further reading:

• Prefix sum on Wikipedia for the mathematical foundations and parallel scan variants
• GeeksforGeeks: Prefix Sum Array for implementation details and applications
• LeetCode 303: Range Sum Query - Immutable for the basic pattern
• LeetCode 560: Subarray Sum Equals K for the hashmap variant
• LeetCode 304: Range Sum Query 2D - Immutable for the 2D extension

Internal links:

• If you're deciding between prefix sum and sliding window, the sliding window algorithm explained covers when the window invariant holds.
• The hashmap component relies on O(1) lookups. Hash map time complexity explains the amortized analysis behind that assumption.