Pattern Guide
Prefix Sum & Difference Array
"Precompute prefix sums. Any range query becomes O(1)."
Prefix sums answer range queries in O(1) after O(n) preprocessing. Difference arrays do range updates in O(1). Together they solve most subarray/interval problems that sliding window can't handle (negatives, non-contiguous constraints).
14 min readdp problems →
Problems you can solve with this pattern
8 problems · click any to start solving
1D prefix sum template
// Build: O(n)
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
// Query sum of nums[l..r] (0-indexed, inclusive): O(1)
const rangeSum = (l, r) => prefix[r+1] - prefix[l];
// Common usage: check if subarray sum === target
// sum(l..r) = target → prefix[r+1] - prefix[l] = target → prefix[l] = prefix[r+1] - target
// So: track seen prefix sums in a hashmap!
const countSubarraysWithSum = (nums, target) => {
const prefix = new Map([[0, 1]]); // prefix sum 0 seen once (before start)
let count = 0, sum = 0;
for (const n of nums) {
sum += n;
count += (prefix.get(sum - target) ?? 0);
prefix.set(sum, (prefix.get(sum) ?? 0) + 1);
}
return count;
};Prefix sum is the most underused O(1) trick in competitive programming. Build it once in O(n), then answer any "sum of nums[i..j]" in O(1). The difference array is the inverse: instead of querying, it does range updates in O(1). Together they handle range sum queries, 2D queries, and interval coverage problems that nested loops would solve in O(n²).
Prefix Sum — Range Query in O(1)
1D prefix sum template
// Build: O(n)
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
// Query sum of nums[l..r] (0-indexed, inclusive): O(1)
const rangeSum = (l, r) => prefix[r+1] - prefix[l];
// Common usage: check if subarray sum === target
// sum(l..r) = target → prefix[r+1] - prefix[l] = target → prefix[l] = prefix[r+1] - target
// So: track seen prefix sums in a hashmap!
const countSubarraysWithSum = (nums, target) => {
const prefix = new Map([[0, 1]]); // prefix sum 0 seen once (before start)
let count = 0, sum = 0;
for (const n of nums) {
sum += n;
count += (prefix.get(sum - target) ?? 0);
prefix.set(sum, (prefix.get(sum) ?? 0) + 1);
}
return count;
};Prefix Sum + Hashmap (the two-sum pattern)
Key insight for "count subarrays with sum = k":
sum(l..r) = k means prefix[r] - prefix[l-1] = k, i.e., prefix[l-1] = prefix[r] - k.
For each position r, look up how many past prefix sums equal prefix[r] - k.
Same pattern as two-sum: use a hashmap to count occurrences.
Why this beats sliding window: works with NEGATIVE numbers (sliding window requires all-positive for monotonicity).
sum(l..r) = k means prefix[r] - prefix[l-1] = k, i.e., prefix[l-1] = prefix[r] - k.
For each position r, look up how many past prefix sums equal prefix[r] - k.
Same pattern as two-sum: use a hashmap to count occurrences.
Why this beats sliding window: works with NEGATIVE numbers (sliding window requires all-positive for monotonicity).
Difference Array — Range Updates in O(1)
Difference array — O(1) updates, O(n) to reconstruct
// Add delta to all nums[l..r] in O(1)
const diff = new Array(n + 1).fill(0);
const rangeAdd = (l, r, delta) => {
diff[l] += delta;
diff[r + 1] -= delta; // stop adding after r
};
// Reconstruct original array after all updates: O(n)
const result = new Array(n).fill(0);
let running = 0;
for (let i = 0; i < n; i++) {
running += diff[i];
result[i] = running;
}
// Use case: "apply k range updates, then query each element"
// Without diff array: O(k·n). With diff array: O(k + n).2D Prefix Sum
2D prefix sum — O(1) rectangle sum query
// Build: prefix[i][j] = sum of rectangle (0,0) to (i-1,j-1)
const buildPrefix2D = (matrix) => {
const m = matrix.length, n = matrix[0].length;
const p = Array.from({length:m+1}, () => new Array(n+1).fill(0));
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
p[i][j] = matrix[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
return p;
};
// Query sum of rectangle (r1,c1) to (r2,c2) — 0-indexed: O(1)
const query2D = (p, r1, c1, r2, c2) =>
p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];Prefix sum checklist:
- "Sum of subarray" → prefix[r+1] - prefix[l]
- "Count subarrays with sum = k" → prefix map (two-sum trick)
- "Subarray sum divisible by k" → prefix mod k (two-sum trick with modulo)
- "Range updates + query each element" → difference array
- "2D rectangle sum" → 2D prefix sum with inclusion-exclusion
- Input has negatives → sliding window fails → use prefix sum + hashmap
- "Product except self" → prefix product + suffix product (same idea, multiplication)
- "Sum of subarray" → prefix[r+1] - prefix[l]
- "Count subarrays with sum = k" → prefix map (two-sum trick)
- "Subarray sum divisible by k" → prefix mod k (two-sum trick with modulo)
- "Range updates + query each element" → difference array
- "2D rectangle sum" → 2D prefix sum with inclusion-exclusion
- Input has negatives → sliding window fails → use prefix sum + hashmap
- "Product except self" → prefix product + suffix product (same idea, multiplication)