Prefix Sum¶
Also known as: Cumulative Sum, Running Sum, Prefix Array
Precompute a running total so that the sum of any range becomes one subtraction. You pay O(n) once and every later range-sum query is free. Combined with a hash map, it solves a whole family of "count the subarrays that sum to K" problems that look impossible at first glance.
Before you start¶
- Comfortable using basic arrays and hash maps in your language.
What 'solved properly' looks like
Target: O(n) preprocessing, O(1) per range query. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
Build a new array where each position i stores the sum of all elements from index 0 to i. Once you have that, the sum of any range [L, R] is simply prefix[R] minus prefix[L-1] — one subtraction instead of a loop. The same prefix array, paired with a hash map of cumulative sums seen so far, also lets you count how many subarrays have a target sum in a single pass.
Why it matters: It turns "sum this range" from an O(n) loop into O(1) arithmetic, which makes it indispensable for problems with many range queries. And the prefix-sum-plus-hash-map trick is the gateway to a whole class of subarray-counting problems that look like they need nested loops but are actually linear.
When to reach for it¶
Reach for it when you need many range-sum queries on an unchanging array, "subarray sums equal K," "count subarrays with a given property," a pivot or equilibrium index, or anything where you'd otherwise add the same numbers repeatedly.
When not to use it
Prefix sum is useless if the array changes between queries — that's a Fenwick tree or segment tree. Also: when every number is positive and you need a contiguous range with a target sum, sliding window does it in O(1) extra space. Prefix sum earns its memory when negatives are in play or you need arbitrary range queries rather than a single sliding condition.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Find Pivot Index | LeetCode | Easy | 15 mins | teaching |
| 2 | Find the Highest Altitude | LeetCode | Easy | 15 mins | teaching |
| 3 | Range Sum Query — Immutable | LeetCode | Easy | 20 mins | consolidation |
| 4 | Product of Array Except Self | LeetCode | Medium | 30 mins | consolidation |
| 5 | Subarray Sum Equals K | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Subarray Sum Equals K cleanly in one sitting — handling the hash-map accumulation correctly without off-by-one errors on the prefix — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.