advanced pattern

Prefix Sum

Pre-compute cumulative sums to answer range queries in O(1) time. Essential for subarray sum problems.

Time

O(n) build, O(1) query

Space

O(n)

🧠Mental Model

“Running total on a receipt - each line shows cumulative spent so far. To find spending between items 3-7, subtract total at item 2 from total at item 7.”

Verbal cue: Build once, query many times in constant time.

🎯Recognition Triggers

When you see these patterns in a problem, consider this approach:

subarray sumrange sum querycumulativesum between indicescontiguous elements sum

📝Code Template

Prefix Sum Template

1function buildPrefixSum(nums) {
2  const prefix = [0];
3  for (let i = 0; i < nums.length; i++) {
4    prefix.push(prefix[i] + nums[i]);
5  }
6  return prefix;
7}
8
9function rangeSum(prefix, left, right) {
10  return prefix[right + 1] - prefix[left];
11}

Complexity rationale: Linear time to build prefix array, then constant time for any range query.

💡Interview Tips

1Mention the trade-off: O(n) space for O(1) queries
2Prefix sum works for XOR, product (with division), and other associative operations
3Can extend to 2D for matrix queries

⚠️Common Mistakes

✕Off-by-one errors in prefix indexing
✕Forgetting the leading 0 in prefix array
✕Not handling negative numbers correctly