Lesson 07 of 2414 min read

Prefix Sums and Counting

Precompute once, answer range questions instantly. Combine it with a hash map and you can count subarrays that sum to a target in linear time.

By the end: Answer range-sum questions in O(1) after an O(n) setup.

You are asked for the sum of a range, many times, on an array that does not change. Computing each range by looping is O(n) per query. Precompute once and every answer becomes O(1).

The idea

Build an array where prefix[i] is the sum of everything before index i. Then the sum from i to j inclusive is prefix[j+1] - prefix[i]: the total up to the end of the range, minus the part you do not want.

Building and using a prefix sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function buildPrefix(nums) {
  // One extra slot at the front, holding 0. This removes every edge case.
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;
}

const nums = [3, 1, 4, 1, 5, 9, 2, 6];
const prefix = buildPrefix(nums);

console.log('nums:  ', nums);
console.log('prefix:', prefix);

const rangeSum = (i, j) => prefix[j + 1] - prefix[i];

console.log('sum(0..0) =', rangeSum(0, 0), '(expect 3)');
console.log('sum(1..3) =', rangeSum(1, 3), '(expect 1+4+1 = 6)');
console.log('sum(0..7) =', rangeSum(0, 7), '(expect 31)');
console.log('sum(4..6) =', rangeSum(4, 6), '(expect 5+9+2 = 16)');

Output

The cost, compared

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function buildPrefix(nums) {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;
}

function sumByLooping(nums, i, j) {
  let s = 0, ops = 0;
  for (let k = i; k <= j; k++) { s += nums[k]; ops++; }
  return { s, ops };
}

const big = Array.from({ length: 10000 }, (_, i) => i % 7);
const pre = buildPrefix(big);

console.log('looping, one full-range query:', sumByLooping(big, 0, 9999).ops, 'operations');
console.log('prefix,  one full-range query: 1 subtraction →', pre[10000] - pre[0]);
console.log('1000 queries by looping: about', (1000 * 10000).toLocaleString('en-US'), 'operations');
console.log('1000 queries with prefix: 10000 to build, then 1000 subtractions');

Output

Where it gets interesting: prefix plus a hash map

This combination answers a whole family of counting questions and it is worth understanding deeply, not memorising.

The question: how many subarrays sum to exactly k? A subarray from i to j sums to k when prefix[j+1] - prefix[i] = k, which rearranges to prefix[i] = prefix[j+1] - k.

So as you walk along computing the running sum, ask: how many earlier prefix values equal (current sum minus k)? Each one is a subarray ending here that works. A map of prefix-value to how-many-times-seen answers that in O(1).

Counting subarrays that sum to k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23function countSubarraysSummingTo(nums, k) {
  const seen = new Map([[0, 1]]);   // a prefix sum of 0 has occurred once: before we start
  let running = 0, count = 0;
  const trace = [];

  for (let i = 0; i < nums.length; i++) {
    running += nums[i];
    const need = running - k;
    const hits = seen.get(need) ?? 0;
    if (hits > 0) trace.push(`at index ${i}: running=${running}, need=${need}, found ${hits}`);
    count += hits;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return { count, trace };
}

const r1 = countSubarraysSummingTo([1, 1, 1], 2);
console.log('[1,1,1] k=2 →', r1.count);
r1.trace.forEach(t => console.log('  ' + t));

console.log('[1,2,3] k=3 →', countSubarraysSummingTo([1, 2, 3], 3).count);          // 2
console.log('[1,-1,0] k=0 →', countSubarraysSummingTo([1, -1, 0], 0).count);        // 3
console.log('[3,4,7,2,-3,1,4,2] k=7 →', countSubarraysSummingTo([3,4,7,2,-3,1,4,2], 7).count); // 4

Output

The same idea, three variations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40// 1. Does any subarray sum to k? Just check, do not count.
function hasSubarraySummingTo(nums, k) {
  const seen = new Set([0]);
  let running = 0;
  for (const x of nums) {
    running += x;
    if (seen.has(running - k)) return true;
    seen.add(running);
  }
  return false;
}
console.log('any subarray of [1,2,3] summing to 5?', hasSubarraySummingTo([1, 2, 3], 5));
console.log('...to 7?', hasSubarraySummingTo([1, 2, 3], 7));

// 2. The LONGEST subarray summing to k: store the FIRST index of each prefix.
function longestSubarraySummingTo(nums, k) {
  const firstIndex = new Map([[0, -1]]);
  let running = 0, best = 0;
  for (let i = 0; i < nums.length; i++) {
    running += nums[i];
    if (firstIndex.has(running - k)) best = Math.max(best, i - firstIndex.get(running - k));
    if (!firstIndex.has(running)) firstIndex.set(running, i);   // first only: keeps it longest
    }
  return best;
}
console.log('longest summing to 3 in [1,-1,5,-2,3]:', longestSubarraySummingTo([1,-1,5,-2,3], 3));  // 4

// 3. Subarray sum divisible by k: group prefixes by remainder.
function countDivisibleBy(nums, k) {
  const counts = new Map([[0, 1]]);
  let running = 0, total = 0;
  for (const x of nums) {
    running += x;
    const mod = ((running % k) + k) % k;      // keep it non-negative
    total += counts.get(mod) ?? 0;
    counts.set(mod, (counts.get(mod) ?? 0) + 1);
  }
  return total;
}
console.log('subarrays of [4,5,0,-2,-3,1] divisible by 5:', countDivisibleBy([4,5,0,-2,-3,1], 5));  // 7

Output

Prefix products, and the divide-free trick

Product of all elements except self, without division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function productExceptSelf(nums) {
  const n = nums.length;
  const out = new Array(n).fill(1);

  // Left pass: out[i] holds the product of everything to the LEFT of i.
  let running = 1;
  for (let i = 0; i < n; i++) { out[i] = running; running *= nums[i]; }

  // Right pass: multiply in the product of everything to the RIGHT.
  running = 1;
  for (let i = n - 1; i >= 0; i--) { out[i] *= running; running *= nums[i]; }

  return out;
}

console.log(productExceptSelf([1, 2, 3, 4]));      // [24,12,8,6]
console.log(productExceptSelf([-1, 1, 0, -3, 3])); // [0,0,9,0,0]
console.log(productExceptSelf([2, 3]));            // [3,2]

Output

Two passes, O(n) time, and the output array is the only allocation. Dividing the total product by each element would be shorter but breaks on zeroes, and interviewers ask for this one specifically to see whether you reach for the two-pass structure.

Difference arrays: many range updates, one final read

The mirror image of a prefix sum. If you need to add a value to many ranges and only read the array at the end, record each range as a +v at the start and a -v just past the end, then take a prefix sum once.

Range updates in O(1) each

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function applyRangeUpdates(length, updates) {
  const diff = new Array(length + 1).fill(0);

  for (const [from, to, value] of updates) {
    diff[from] += value;
    diff[to + 1] -= value;         // cancels the addition beyond the range
  }

  // One prefix sum turns the marks into the real values.
  const out = new Array(length);
  let running = 0;
  for (let i = 0; i < length; i++) { running += diff[i]; out[i] = running; }
  return out;
}

console.log(applyRangeUpdates(5, [[1, 3, 2], [2, 4, 3], [0, 0, -2]]));
// index:      0   1  2  3  4
// expect:    -2   2  5  5  3

// The naive version costs O(range length) per update; this is O(1) per update
// plus one final O(n) pass.
console.log(applyRangeUpdates(10, [[0, 9, 1], [0, 9, 1], [5, 5, 8]]));

Output

Two dimensions

2D prefix sums for rectangle queries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function build2D(grid) {
  const rows = grid.length, cols = grid[0].length;
  const p = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      p[r + 1][c + 1] = grid[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c];
  return p;
}

// Sum of the rectangle from (r1,c1) to (r2,c2) inclusive: add the big block,
// subtract the strip above and the strip left, add back the corner counted twice.
function rectSum(p, r1, c1, r2, c2) {
  return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
}

const grid = [
  [3, 0, 1, 4],
  [5, 6, 3, 2],
  [1, 2, 0, 1],
];
const p = build2D(grid);

console.log('whole grid:', rectSum(p, 0, 0, 2, 3), '(expect 28)');
console.log('single cell (1,1):', rectSum(p, 1, 1, 1, 1), '(expect 6)');
console.log('middle 2x2 (1,1)-(2,2):', rectSum(p, 1, 1, 2, 2), '(expect 6+3+2+0 = 11)');

Output

Recognising it

Repeated range sum or range average queries on an unchanging array.
Count the subarrays whose sum equals, or is divisible by, something.
Many range updates and one final read, which is a difference array.
An answer at each position that depends on everything to the left and everything to the right, which is the two-pass shape.

If the array does change between queries, a prefix sum is the wrong tool: rebuilding is O(n) per update. That is what a Fenwick tree or a segment tree is for, and it is fair to name them and say you would reach for one, which is usually enough in an interview.

Your turn: four prefix problems

runningSum(nums) — the warm-up: return the prefix sums in place.
pivotIndex(nums) — the index where the sum to the left equals the sum to the right, or -1.
findMaxLength(nums) — the longest subarray of 0s and 1s with equal counts of each. Trick: treat 0 as -1 and find the longest subarray summing to 0.
carPooling(trips, capacity) — each trip is [passengers, start, end]; can the bus carry them all? A difference array over the stops.

Editable. Fill them in, then run.

function runningSum(nums) {
  // your code
}

function pivotIndex(nums) {
  // total, then walk keeping leftSum
}

function findMaxLength(nums) {
  // map running sum → first index; count 0 as -1
}

function carPooling(trips, capacity) {
  // diff[start] += p; diff[end] -= p; then prefix and check
}

console.log(runningSum([1, 2, 3, 4]));                  // [1,3,6,10]
console.log(pivotIndex([1, 7, 3, 6, 5, 6]));            // 3
console.log(pivotIndex([1, 2, 3]));                     // -1
console.log(findMaxLength([0, 1]));                     // 2
console.log(findMaxLength([0, 1, 0]));                  // 2
console.log(findMaxLength([0,1,1,0,1,1,1,0]));          // 4
console.log(carPooling([[2,1,5],[3,3,7]], 4));          // false
console.log(carPooling([[2,1,5],[3,3,7]], 5));          // true

Output

Recap

A prefix array with a leading zero makes any range sum a single subtraction: prefix[j+1] - prefix[i].
Prefix sum plus a hash map counts subarrays with a target sum in one pass; seed the map with 0 → 1.
Store counts to count subarrays, but store the earliest index to find the longest one.
In JavaScript take remainders as ((x % k) + k) % k, because % keeps the sign.
A difference array makes each range update O(1), paid for by one prefix pass at the end.

The idea

Where it gets interesting: prefix plus a hash map

Prefix products, and the divide-free trick

Difference arrays: many range updates, one final read

Two dimensions

Recognising it

Your turn: four prefix problems

Recap

New writing, when it lands.