DSA · Patterns, not puzzles
What are prefix sums and when are they useful?
Short answer
A prefix sum stores the running total up to each index, so any range sum is the difference of two prefix values. Combined with a hash map, it answers subarray-sum queries in one pass.
The naive range sum loops over the range. A prefix array precomputes cumulative totals once, then each range sum is O(1). The technique generalises to products, counts and two-dimensional grids.
function buildPrefix(values) {
const prefix = new Array(values.length + 1).fill(0);
for (let i = 0; i < values.length; i++) {
prefix[i + 1] = prefix[i] + values[i];
}
return prefix;
}
function rangeSum(prefix, left, right) {
return prefix[right + 1] - prefix[left];
}The subarray-sum trick
If prefix[j] - prefix[i] equals k, then the subarray between i and j sums to k. While scanning, store how many times each prefix value has appeared. For each new prefix, add the count of prefix - k.
function subarraySum(values, target) {
const counts = new Map([[0, 1]]);
let prefix = 0;
let total = 0;
for (const value of values) {
prefix += value;
total += counts.get(prefix - target) || 0;
counts.set(prefix, (counts.get(prefix) || 0) + 1);
}
return total;
}Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1How do you extend prefix sums to two dimensions?
- 2Why seed the map with zero?
- 3What data structure would you use if values change between queries?
- 4How does this handle negative numbers?
Say it in the interview
A prefix sum is a running total where each entry represents the sum from the start to that index. A range sum becomes the difference of two prefix entries, so queries are constant time after linear preprocessing. With a hash map, I can count subarrays with a target sum in one pass by looking for prefix minus target. Negative values are fine, but frequent updates would call for a Fenwick or segment tree.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.