Precompute cumulative sums to answer range queries in O(1) time.
The prefix sum pattern transforms an array into a cumulative sum array, where each element stores the total of all elements from the beginning up to that index. Once built, any range sum query becomes a single subtraction instead of a loop.
Build a prefix array where prefix[i] = sum of elements from index 0 to i. Then any range sum [l, r] = prefix[r] - prefix[l-1].
Think of it like odometer readings. To find the distance between two points, you subtract the starting reading from the ending reading. Prefix sums work the same way: subtract the cumulative sum at the start from the cumulative sum at the end.
Look for these signals in a problem:
Each cell in the prefix array accumulates the running total. The formula is simple: prefix[i] = prefix[i-1] + nums[i]. Let's watch it build step by step from [1, 2, 3, 4, 5, 6].
Practical tip: Use a prefix array of size n + 1 with prefix[0] = 0. This eliminates the edge case when the range starts at index 0, since prefix[r+1] - prefix[l] always works without special checks.
Let's query the sum of elements from index 2 to 4 in our array [1, 2, 3, 4, 5, 6]. Using the size n+1 prefix array convention:
Using prefix[0] = 0 convention: rangeSum = prefix[r+1] - prefix[l]
Verify: 3 + 4 + 5 = 12. No loop needed, just one subtraction.
For problems like "count subarrays with sum = k", we combine prefix sums with a HashMap. The key insight: if prefix[j] - prefix[i] = k, then the subarray from i+1 to j sums to k.
As we scan left to right computing the running sum, at each position j we ask: "Have I seen a prefix sum equal to currentSum - k before?" If yes, the subarray between that earlier position and j has sum exactly k.
The HashMap stores how many times each prefix sum has occurred, so we count all valid starting points in O(1).
| INDEX | NUM | SUM | SUM-K | IN MAP? | COUNT |
|---|---|---|---|---|---|
| init | - | 0 | - | - | 0 |
| 0 | 1 | 1 | -5 | no | 0 |
| 1 | 2 | 3 | -3 | no | 0 |
| 2 | 3 | 6 | 0 | YES (1x) | 1 |
| 3 | -2 | 4 | -2 | no | 1 |
| 4 | 5 | 9 | 3 | YES (1x) | 2 |
Found 2 subarrays with sum = 6: [1,2,3] and [3,-2,5].
// Subarray sum equals k (with HashMap) Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); // empty prefix has sum 0 int sum = 0, count = 0; for (int num : nums) { sum += num; // running prefix sum // How many earlier prefixes had sum = (sum - k)? count += map.getOrDefault(sum - k, 0); // Record this prefix sum map.merge(sum, 1, Integer::sum); }
Why put(0, 1)? We initialize the map with sum 0 having count 1. This handles the case where a subarray starting from index 0 has sum exactly k. Without this, we would miss those subarrays.
For matrix problems, extend the pattern to two dimensions. Each cell prefix[i][j] stores the sum of the submatrix from (0,0) to (i,j).
The red term corrects for the double subtraction of the overlapping rectangle. This is the classic inclusion-exclusion principle.
Here is the complete annotated template covering both the basic prefix sum and the HashMap variant.
// Build prefix sum (size n+1, prefix[0] = 0 for cleaner math) int[] prefix = new int[n + 1]; for (int i = 0; i < n; i++) { prefix[i + 1] = prefix[i] + nums[i]; } // Range sum query [l, r] inclusive — O(1) int rangeSum = prefix[r + 1] - prefix[l];
Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); // base case: empty prefix int sum = 0, count = 0; for (int num : nums) { sum += num; // running prefix sum count += map.getOrDefault(sum - k, 0); map.merge(sum, 1, Integer::sum); } return count;
Practice these problems in order, from the basic range query to more creative applications:
#525 Contiguous Array is a clever twist: treat 0 as -1, then "equal number of 0s and 1s" becomes "subarray sum = 0." This transforms a counting problem into a prefix sum + HashMap problem.
Enter an array, build the prefix sum step by step, then query any range instantly.
Building the prefix array requires a single pass through the input. After that, each range query is a constant-time subtraction. The trade-off is O(n) extra space for the prefix array.
| APPROACH | BUILD | PER QUERY | Q QUERIES |
|---|---|---|---|
| Brute Force | - | O(n) | O(n * Q) |
| Prefix Sum | O(n) | O(1) | O(n + Q) |
When Q queries is large (say Q = 100,000 on an array of n = 100,000), brute force does 10 billion operations while prefix sum does just 200,000. That is the difference between TLE and accepted.
prefix[r+1] - prefix[l] work universally.
currentSum - k for O(n) total time.