Prefix Sum

Precompute cumulative sums for O(1) range queries

O(n) O(n)

Recognition Signals

Problem asks for sum/count in a subarray or range — prefix sum precomputes this

Keywords: 'subarray sum equals K', 'range sum query', 'contiguous array'

Brute force involves nested loops summing subarrays (O(n²)) — prefix sum reduces to O(n)

Problem involves cumulative frequency, running totals, or prefix-based calculations

If you see 'number of subarrays with sum = target', think prefix sum + HashMap

2D range sum queries — apply prefix sum in both dimensions with inclusion-exclusion

Product of array except self — prefix and suffix products are a variant

Pro Tips

Use a HashMap to store prefix sum frequencies for O(1) lookup when target sum is involved

For 2D prefix sums, apply inclusion-exclusion: sum(r1,c1,r2,c2) = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

Watch for integer overflow — use long when summing large arrays

Always initialize HashMap with (0, 1) — the empty prefix has sum 0 with count 1

Contiguous Array (equal 0s and 1s): treat 0 as -1, then find longest subarray with sum 0 using prefix sum

For 'divisible by K': use modular arithmetic on prefix sums; handle negative remainders carefully

Approach

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i-1. To get sum of subarray [l, r], compute prefix[r+1] - prefix[l]. For 'subarray sum equals K' problems, use a HashMap storing prefix sum frequencies.

Code Template

java18 lines

1	// Prefix Sum — Subarray Sum Equals K
2	public int subarraySum(int[] nums, int k) {
3	// Why: HashMap stores how many times each prefix sum has occurred
4	Map<Integer, Integer> prefixCount = new HashMap<>();
5	prefixCount.put(0, 1); // Why: empty prefix has sum 0
6
7	int currentSum = 0;
8	int result = 0;
9
10	for (int num : nums) {
11	currentSum += num;
12	// Why: if (currentSum - k) was seen before, those subarrays sum to k
13	int complement = currentSum - k;
14	result += prefixCount.getOrDefault(complement, 0);
15	prefixCount.merge(currentSum, 1, Integer::sum);
16	}
17	return result;
18	}

Problems (10)

Running Sum of 1d Array

easyleetcode

Range Sum Query - Immutable

easyleetcode

Find Pivot Index

easyleetcode

Subarray Sum Equals K

mediumleetcode

Contiguous Array

mediumleetcode

Product of Array Except Self

mediumleetcode

Range Sum Query 2D - Immutable

mediumleetcode

Subarray Sums Divisible by K

mediumleetcode

Maximum Size Subarray Sum Equals K

hardleetcode

Count Subarrays With Score Less Than K

hardleetcode