Prefix Sum Pattern

When to use Prefix Sum

• You face many range-sum queries against an array that does not mutate between queries.
• You need to count or find subarrays whose sum equals (or is divisible by) a target k.
• You are computing 'product of all except self' or any aggregate where each index needs the running combination of everything before or after it.
• The problem extends to 2D and asks for sub-matrix sums — a 2D prefix-sum table answers each rectangle query in O(1).
• You need to detect a continuous subarray whose sum is a multiple of k, using prefix sums modulo k as hash keys.

Template

function subarraySum(nums, k) {
  const seen = new Map();
  seen.set(0, 1);
  let prefix = 0;
  let count = 0;
  for (const num of nums) {
    prefix += num;
    if (seen.has(prefix - k)) {
      count += seen.get(prefix - k);
    }
    seen.set(prefix, (seen.get(prefix) || 0) + 1);
  }
  return count;
}

Common mistakes

• Forgetting to seed the hash map with `seen.set(0, 1)` before the loop — subarrays that start at index 0 require an empty-prefix entry to be counted.
• Confusing 'count of subarrays with sum k' (Subarray Sum Equals K) with 'longest subarray with sum k' (a different variant) — the first uses += count, the second uses earliest index.
• Building a prefix array of length n instead of n + 1 and then forgetting to subtract `prefix[i] - prefix[i-1]`, producing off-by-one errors on ranges that include index 0.
• On Product of Array Except Self, computing total product then dividing — fails on inputs containing zero. The correct approach uses two passes (left prefix, right suffix) and avoids division entirely.
• On Continuous Subarray Sum (mod k variant), comparing prefix sums directly instead of `prefix % k`, missing all cases where the difference is a multiple of k but not equal to k itself.