Prefix Sums & Running Aggregates

MNEMONIC Range = difference of prefixes. Count = seen a prefix before?

PATTERN What this technique is really about

Prefix sums attack any problem built on cumulative totals over ranges. The unifying idea: spend O(n) up front to compute a running aggregate, then answer each range or subarray question by reusing it instead of re-summing.

It shows up in three escalating forms:

• 1D prefix array → range queries. Precompute P; every sum(i..j) is one subtraction. O(1) per query after O(n) setup.
• Running prefix + hash map → subarray counts.Carry the prefix and a map of prefixes seen; “count subarrays = k” becomes a complement lookup. Works with negatives, where sliding windows can't.
• Prefix × suffix → “all except self”. The aggregate is a product; combine the product before i with the product after it — no division needed.

It reaches across categories: Kadane's algorithm (Maximum Subarray) is a running aggregate with a reset — a doorway into DP — and the positive-values window contrast lands squarely in Sliding Window.

KEY IDEA Range = difference of prefixes; count = "seen prefix" hashing

That second form is the powerhouse. Carrying the running prefix and a map from prefix total → count of occurrences turns subarray counting into a single O(n) pass. Because it looks up an exact complement rather than relying on the sum being monotonic, it survives negatives that would invalidate a sliding window.

The discipline: seed the map with map.set(0, 1) so a prefix that itself equals k (a subarray starting at index 0) is counted, and file the current prefix after querying so you never match a zero-length range.

COST Complexity profile

Space is O(n) for a prefix array or the prefix-count map. The prefix × suffix product variant can run in O(1) extra space (reusing the output array). The win scales with how many overlapping ranges you'd otherwise re-sum.

VARIANTS The three forms at a glance

• 1D prefix array. Static array, many range-sum queries → build P once, subtract per query.
• Prefix + hashmap. Count / locate subarrays with a sum (or modular, or parity) property over a running total → complement lookup on seen prefixes.
• Prefix × suffix products. “Combine everything except position i” → multiply the prefix product by the suffix product.

The same skeleton generalizes further: 2D prefix sums (integral images) for submatrix sums, prefix XOR for “subarrays with XOR = k”, and prefix-of-differences for range-update / point-query problems (difference arrays).

RUN IT Have I seen sum − k before?

1function subarraySum(nums: number[], k: number): number {
2▶  // seen[p] = how many times prefix total p has occurred
3▶  const seen = new Map<number, number>([[0, 1]]); // base case
4▶  let sum = 0, count = 0;
5 
6  for (let i = 0; i < nums.length; i++) {
7    sum += nums[i];                       // extend running prefix
8    const need = sum - k;                 // complement we hope to have seen
9    count += seen.get(need) ?? 0;         // every earlier match = one subarray
10    seen.set(sum, (seen.get(sum) ?? 0) + 1); // file this prefix for later
11  }
12  return count;
13}

TRIGGERS When you see ___ → reach for ___

Reach for prefix sums when a problem is about ranges, subarrays, or a running total, especially when you'd otherwise re-sum overlapping ranges. Add the hash map the instant the question becomes count / find subarrays with a sum property — particularly with negatives in the array.

RED FLAGSWhen it's NOT this pattern

• All values are positive and you want the longest/shortest subarray. A sliding window is simpler and runs in O(1) extra space — the monotonic growth of the sum lets you advance one pointer and never backtrack. Minimum Size Subarray Sum is the canonical case. Prefix + hash map still works but is overkill here.
• The array mutates between queries. A plain prefix array is invalidated by any update. If you need range queries and point updates, reach for a Fenwick tree (BIT) or segment tree instead.
• You only ever ask one range sum. Building a whole prefix array to answer a single query is wasted O(n) space — just sum that one range.

TEMPLATE Prefix array + range query

When → A fixed array with many range-sum queries. Pay O(n) once to build the cumulative array, then answer each sum(i..j) in O(1).

// 1. Build a prefix array once — O(n)
// P[i] = sum of nums[0..i-1];  P[0] = 0  (empty prefix)
function buildPrefix(nums: number[]): number[] {
  const P = new Array<number>(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) P[i + 1] = P[i] + nums[i];
  return P;
}

// 2. Any range sum is now ONE subtraction — O(1) per query
// sum of nums[i..j] (inclusive) = P[j + 1] - P[i]
function rangeSum(P: number[], i: number, j: number): number {
  return P[j + 1] - P[i];
}

TEMPLATE Running prefix + hashmap of counts

When → Count or locate subarrays whose sum satisfies a property — the textbook subarray-sum-equals-k. The map makes the complement lookup O(1), and it tolerates negatives.

// Count subarrays summing to k — O(n), works WITH negatives.
function subarraySum(nums: number[], k: number): number {
  // seen[p] = how many times prefix total p has occurred so far
  const seen = new Map<number, number>([[0, 1]]); // base case is mandatory
  let sum = 0, count = 0;

  for (const n of nums) {
    sum += n;                                  // extend running prefix
    // a subarray ending here sums to k  ⇔  some earlier prefix = sum - k
    count += seen.get(sum - k) ?? 0;           // each earlier match = 1 subarray
    seen.set(sum, (seen.get(sum) ?? 0) + 1);   // file this prefix for the future
  }
  return count;
}

TEMPLATE Prefix × suffix products

When → Combine everything except position i — classically product of array except self without division. Generalizes the prefix idea from + to ×.

// Product of array except self — no division, O(n) time, O(1) extra space.
function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const res = new Array<number>(n).fill(1);

  // 1. Left→right: res[i] = product of everything BEFORE i (prefix product)
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    res[i] = prefix;
    prefix *= nums[i];
  }

  // 2. Right→left: multiply in the product of everything AFTER i (suffix product)
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    res[i] *= suffix;
    suffix *= nums[i];
  }
  return res;
}

PITFALL Forgetting to seed the map with { 0: 1 }

The prefix-count map must start with map.set(0, 1). Without it, any subarray that starts at index 0 and sums to k is missed — there's no “previous prefix” entry equal to 0 to match the running sum against. This is the single most common bug in subarray-sum-equals-k.

PITFALL Off-by-one between P[i] and P[i+1]

With the convention P[0] = 0 and P[k] = nums[0] + … + nums[k−1], the inclusive range nums[i..j] is P[j+1] − P[i] — not P[j] − P[i]. Mixing the 0-based array index with the 1-based prefix index drops the first or last element. Pick one convention and write the formula down.

PITFALL Reaching for a sliding window when the array has negatives

A sliding window relies on the running sum being monotonic: growing the window can only grow the sum, so you can advance one pointer and never backtrack. A single negative number breaks that — a longer window may have a smaller sum — so the window can't decide whether to grow or shrink. Prefix + hash map looks up the exact complement and doesn't care about sign, which is why it's the correct tool for subarray-sum-equals-k with negatives.

PITFALL Integer overflow on large running sums or products

A running prefix over up to 10⁵ elements with large values can exceed a 32-bit integer, and products blow up far faster. In JavaScript/TypeScript, numbers are IEEE-754 doubles (safe integers to 2⁵³) so sums are usually fine, but in typed languages use a 64-bit type, and for products consider BigInt or modular arithmetic. Always read the constraints before assuming the aggregate fits.

PROBLEMS