Prefix Sum: when to spot it, explain it, and practice it
Prefix sum is the simplest way to stop recomputing overlapping ranges. The pattern becomes especially powerful when the prefix is paired with a hash map to count or locate target differences.
Pattern coverage
35+
Best first move
Pick whether you need a raw prefix array or prefix + hash map.
Common failure point
Inclusive/exclusive indices are mixed up.
When this pattern should come to mind
Checklist before you code
The solving flow that works well in interviews
Define what the cumulative state means.
Build the prefix in one forward pass.
Rewrite the target condition into a difference of prefix states.
If counting, store prior prefixes in a map before or after checking based on the problem.
Use the derived difference to update the answer in O(1) per step.
Common variants
Range query
Use prefix arrays to answer repeated range-sum questions quickly.
Prefix + hash map
Count or locate subarrays by looking up prior prefix states.
2D prefix sum
Compress rectangle-sum queries in matrices.
Template preview
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
range_sum = prefix[r + 1] - prefix[l]
Classic problems with useful framing
#560
Subarray Sum Equals K
Best starter for prefix + hash-map counting.
Count subarrays whose sum equals k.
#303
Range Sum Query - Immutable
The canonical range-query prefix-sum problem.
Answer many immutable range-sum queries quickly.
#974
Subarray Sums Divisible by K
Great for modulo normalization practice.
Count subarrays whose sum is divisible by k.
#304
Range Sum Query 2D - Immutable
Extends 1D intuition to matrix queries.
Answer rectangle sum queries on a matrix.
A more useful problem ladder for practice
This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.
Foundation
#303 Range Sum Query - Immutable
Answer many immutable range-sum queries quickly.
The sum of [l, r] is just prefix[r + 1] - prefix[l].
Foundation
#49 Group Anagrams
Group strings that are anagrams of each other.
Two strings belong to the same group exactly when their normalized character-count signatures match.
Variant depth
#238 Product of Array Except Self
Return an array where each value is the product of all other elements.
You never need division if you build left products and then sweep from the right.
Variant depth
#304 Range Sum Query 2D - Immutable
Answer rectangle sum queries on a matrix.
Every rectangle sum is the big prefix minus two overlaps plus the shared corner prefix.
Pressure test
#560 Subarray Sum Equals K
Count subarrays whose sum equals k.
The hash map stores counts of past prefix sums, not intervals themselves.
Pressure test
#974 Subarray Sums Divisible by K
Count subarrays whose sum is divisible by k.
You are counting equal remainder classes, not exact prefix sums.
High-frequency mistakes
Inclusive/exclusive indices are mixed up.
Hash-map update timing is wrong for count-based problems.
Modulo keys are not normalized, breaking lookups.
Using prefix sum where a sliding window is required for all-positive constraints.
Recommended practice path
Start with range sum query and immutable arrays.
Then solve subarray sum equals k.
Add modulo-based prefix questions next.
Finish with tree or matrix prefix-sum variants.