When to use. Many range queries, subarray sums, or 2D grids of range sums.
Complexity. Time Build O(n); each query O(1). Space O(n) for the prefix array.
Who gets asked. Range-sum warmup is intern. Subarray-sum-equals-k with a prefix map is the usual follow-up.
Prereq. Arrays; hash tables if you need “prefix seen before”.
Prefix Sums
Store running totals so a range is two lookups. Pair with a hash map when the question is “has this prefix appeared before?”
The idea
prefix[0] = 0, prefix[i] = nums[0] + … + nums[i−1]. Then sum(l..r inclusive) = prefix[r+1] − prefix[l]. Build once in O(n), query in O(1).
Subarray sum equals target: as you walk, let need = prefix − target. If need was seen as an earlier prefix, a subarray exists. Store prefix → count (or index).
2D grids use a summed-area table: include up and left, subtract the overlap. Difference arrays are the inverse — range updates in O(1), then one prefix pass.
Worked example
Count subarrays with sum k
Integer array (can be negative) and k. How many contiguous subarrays sum to k? Example: [1, 2, 1, −1], k = 3 → 2 ([1,2] and [2,1]).
Walk left to right, keep running prefix.
Add how many times (prefix − k) was seen.
Then record the current prefix in the map. Seed the map with 0 → 1 for subarrays that start at index 0.
function countSubarraysSumK(nums, k) {
const seen = new Map([[0, 1]]);
let prefix = 0;
let total = 0;
for (const n of nums) {
prefix += n;
total += seen.get(prefix - k) || 0;
seen.set(prefix, (seen.get(prefix) || 0) + 1);
}
return total;
}
Time O(n). Space O(n) for distinct prefixes.
Practice shapes
Original prompts — same family as interview questions, not copied statements.
Range sum API
Preprocess an immutable array so sum between i and j is O(1) after O(n) setup.
Aim: Build O(n), query O(1), space O(n)
Balance point
Index where left-of-i sum equals right-of-i sum, or report none.
Aim: O(n) time, O(1) extra if you keep a total
Grid rectangle sum
Many queries: sum of a sub-rectangle in a 2D grid of numbers.