Part 4 · Lesson 20 · 24 min read
Prefix Sum
Pre-compute running totals so that any range sum is instant.
On this page
Many range sums, one pass
A subarray is a block of items that sit next to each other in an array, like nums[1..3] (the items at index 1, 2 and 3). Many problems ask for the sum of many different subarrays. If you add the items up one by one, each question costs O(n) steps (the steps grow with the array length n):
const nums = [3, 1, 4, 1, 5];function rangeSum(l, r) { // sum of nums[l..r], inclusive let s = 0; for (let i = l; i <= r; i++) s += nums[i]; return s; // O(r - l + 1) for every query}console.log(rangeSum(1, 3)); // 6A query is one question, such as “what is the sum of this range?”. With 105 queries on 105 items, that is 1010 steps, which is far too slow. The fix uses the pre-computation idea from Lesson 15. Pre-computation means you do some work once, before the questions come, and save the result. Here you spend one pass building running totals. After that, every range sum is just one subtraction.
Building the prefix array
A prefix sum array is an array of running totals. In the array pre, the value at position i is the sum of the first i items of nums. A running total is the sum so far, like the total on a shop receipt that grows with each item. pre starts with a 0 (the sum of no items), so it is one item longer than nums:
Traced: build, then answer a range query
We want any range sum to be instant.
▶const nums = [3, 1, 4, 1, 5];2const pre = [0];3for (let i = 0; i < nums.length; i++) {4 pre.push(pre[i] + nums[i]);5}6const l = 1, r = 3;7console.log(pre[r + 1] - pre[l]);| nums | [3, 1, 4, 1, 5] |
The range formula, and why the extra 0
sum(nums[l..r]) = pre[r + 1] - pre[l]
pre[r + 1] is the sum of everything from index 0 to r. pre[l] is the sum of everything from index 0 to l − 1. If you subtract the second from the first, the part before l is removed, and only the range l..r is left. The leading 0 lets ranges that start at index 0 work without a special case: sum(0..r) = pre[r + 1] - pre[0] = pre[r + 1] - 0.
| Range | Formula | Answer | Check |
|---|---|---|---|
| 0..4 | pre[5] − pre[0] = 14 − 0 | 14 | 3+1+4+1+5 |
| 1..3 | pre[4] − pre[1] = 9 − 3 | 6 | 1+4+1 |
| 2..2 | pre[3] − pre[2] = 8 − 4 | 4 | just 4 |
| 3..4 | pre[5] − pre[3] = 14 − 8 | 6 | 1+5 |
Pivot index: left sum vs right sum
Sometimes you do not need the whole prefix array. One running total is enough. The pivot index is the position where the sum of the items on its left equals the sum of the items on its right. If you know the total of all items, the right sum is total - left - nums[i]:
function pivotIndex(nums) { const total = nums.reduce((a, b) => a + b, 0); let left = 0; // sum of everything before i for (let i = 0; i < nums.length; i++) { const right = total - left - nums[i]; // sum of everything after i if (left === right) return i; left += nums[i]; } return -1;}console.log(pivotIndex([1, 7, 3, 6, 5, 6])); // 3 (1 + 7 + 3 = 11 = 5 + 6)console.log(pivotIndex([1, 2, 3])); // -1Prefix and suffix products
The same idea works for multiplication, and from both directions. A prefix product is a running product, and a suffix product is a running product from the right end. Take the problem “the product of every item except nums[i]”. The answer is (the product of everything to the left) × (the product of everything to the right). A pass from the left fills in the left products. A pass from the right multiplies in the right products. You never divide, so zeros cause no problem.
function productExceptSelf(nums) { const n = nums.length; const out = new Array(n).fill(1); let left = 1; for (let i = 0; i < n; i++) { // out[i] = product of everything to the left out[i] = left; left *= nums[i]; } let right = 1; for (let i = n - 1; i >= 0; i--) { // multiply in the product of everything to the right out[i] *= right; right *= nums[i]; } return out;}console.log(productExceptSelf([1, 2, 3, 4])); // [ 24, 12, 8, 6 ]| i | left product | right product | out[i] |
|---|---|---|---|
| 0 | 1 | 2 × 3 × 4 = 24 | 24 |
| 1 | 1 | 3 × 4 = 12 | 12 |
| 2 | 1 × 2 = 2 | 4 | 8 |
| 3 | 1 × 2 × 3 = 6 | 1 | 6 |
Subarray sum equals k: prefix sums + a Map
This is the most important prefix-sum problem: how many subarrays add up to exactly k? Checking every subarray costs O(n²). The prefix idea turns the check into a quick lookup.
A subarray from i to j has the sum pre[j + 1] - pre[i]. We want that sum to equal k. That is the same as pre[i] = pre[j + 1] - k. So as we walk forward with the running sum, we ask: how many earlier prefix sums equal (current sum − k)? A Map is a collection of key and value pairs, and it finds a key very fast. Use a Map that stores how many times each prefix sum has appeared (Lesson 15). Then each question is answered in O(1), which means one quick step.
function subarraySum(nums, k) { const seen = new Map([[0, 1]]); // prefix sum 0 has been "seen" once: before any item let sum = 0, count = 0; for (const x of nums) { sum += x; // prefix sum up to here count += seen.get(sum - k) ?? 0; // earlier prefixes that leave exactly k seen.set(sum, (seen.get(sum) ?? 0) + 1); } return count;}console.log(subarraySum([1, 2, 3], 3)); // 2 ([1, 2] and [3])console.log(subarraySum([1, -1, 1], 1)); // 3 ([1], [1], [1, -1, 1])| x | sum | look for sum − 3 | found | count | seen after |
|---|---|---|---|---|---|
| 0 | 0 | {0: 1} | |||
| 1 | 1 | −2 | 0 | 0 | {0: 1, 1: 1} |
| 2 | 3 | 0 | 1 | 1 | {0: 1, 1: 1, 3: 1} |
| 3 | 6 | 3 | 1 | 2 | {0: 1, 1: 1, 3: 1, 6: 1} |
At sum 3, the earlier prefix 0 gives [1, 2]. At sum 6, the earlier prefix 3 gives [3].
A subarray that starts at index 0 needs the “empty prefix” (sum 0) to subtract. Without this first entry, the subarray [1, 2] above would be missed. This method also works with negative numbers. The sliding window of Lesson 23 does not, because it needs non-negative values.
Practice questions
For each question, decide which you need: the whole prefix array, just one running total, or prefix sums in a Map.
Return the running sum of nums.
Hint 1
Show all 2 solutions with explanations
For each i, add up nums[0..i] from scratch.
function runningSum(nums) { return nums.map((_, i) => nums.slice(0, i + 1).reduce((a, b) => a + b, 0));}console.log(runningSum([1, 2, 3, 4])); // [ 1, 3, 6, 10 ]This is O(n²). The slice and the sum each run a loop that you cannot see.
Add the previous value to each value, in place (inside the same array).
function runningSum(nums) { for (let i = 1; i < nums.length; i++) nums[i] += nums[i - 1]; return nums;}console.log(runningSum([1, 2, 3, 4])); // [ 1, 3, 6, 10 ]console.log(runningSum([3, 1, 2, 10, 1])); // [ 3, 4, 6, 16, 17 ]O(n) time, O(1) extra space. The result is a prefix array without the leading 0.
The whole lesson in one line: reuse the previous total, do not work it out again. (LeetCode 1480.)
Design a class that receives an array once. After that, it must answer many “sum of nums[left..right]” queries quickly.
Hint 1
Show the solution with explanations
Pay O(n) once, answer each query in O(1).
class NumArray { constructor(nums) { this.pre = [0]; for (const x of nums) this.pre.push(this.pre[this.pre.length - 1] + x); } sumRange(left, right) { return this.pre[right + 1] - this.pre[left]; }}const na = new NumArray([-2, 0, 3, -5, 2, -1]);console.log(na.sumRange(0, 2)); // 1console.log(na.sumRange(2, 5)); // -1console.log(na.sumRange(0, 5)); // -3O(n) to build, O(1) per query, O(n) space. Negative values work in the same way.
This is the standard prefix-sum design question. If the array could also be changed later, a prefix array would need O(n) work for each change. Then people use a different structure, such as a Fenwick tree or a segment tree. (LeetCode 303.)
Return the leftmost index where the sum of the values to its left equals the sum of the values to its right. If there is no such index, return −1.
Hint 1
Show the solution with explanations
Work out the total once. Then walk through the array and keep a left sum.
function pivotIndex(nums) { const total = nums.reduce((a, b) => a + b, 0); let left = 0; for (let i = 0; i < nums.length; i++) { if (left === total - left - nums[i]) return i; left += nums[i]; } return -1;}console.log(pivotIndex([1, 7, 3, 6, 5, 6])); // 3console.log(pivotIndex([1, 2, 3])); // -1console.log(pivotIndex([2, 1, -1])); // 0O(n) time, O(1) space. You check before you add nums[i] to left. This keeps the pivot item itself out of both sides.
Look at the edge case in example 3. An index can be the pivot even when one side is empty. (LeetCode 724.)
Return an array where each position holds the product of all the other values. Do it in O(n) time, without division.
Hint 1
Hint 2
Show the solution with explanations
The left pass stores the left product at each place. The right pass multiplies in the right product.
function productExceptSelf(nums) { const n = nums.length; const out = new Array(n); let left = 1; for (let i = 0; i < n; i++) { out[i] = left; left *= nums[i]; } let right = 1; for (let i = n - 1; i >= 0; i--) { out[i] *= right; right *= 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 ]O(n) time, O(1) extra space (the output array does not count). JavaScript prints -0 (“negative zero”) when a negative number is multiplied by 0. In JavaScript -0 === 0 is true, so it is still the correct answer.
This is a classic: prefix and suffix products, with no division. (LeetCode 238.)
Return the number of subarrays whose values add up to exactly k. The values can be negative.
Hint 1
Hint 2
Show all 2 solutions with explanations
For each start, move the end one step at a time and keep a running sum.
function subarraySum(nums, k) { let count = 0; for (let i = 0; i < nums.length; i++) { let s = 0; for (let j = i; j < nums.length; j++) { s += nums[j]; if (s === k) count++; } } return count;}console.log(subarraySum([1, 1, 1], 2)); // 2O(n²) time. It is too slow for 2 × 104 values, but it gives the right answer, so it is a good first version.
The algorithm from the lesson.
function subarraySum(nums, k) { const seen = new Map([[0, 1]]); let sum = 0, count = 0; for (const x of nums) { sum += x; count += seen.get(sum - k) ?? 0; seen.set(sum, (seen.get(sum) ?? 0) + 1); } return count;}console.log(subarraySum([1, 1, 1], 2)); // 2console.log(subarraySum([1, 2, 3], 3)); // 2O(n) time, O(n) space. It works with negative numbers and zeros.
This is one of the most important medium problems. Learn the lines inside the loop by heart. (LeetCode 560.)
You get an array of 0s and 1s. Return the length of the longest subarray that has the same number of 0s and 1s.
Hint 1
Hint 2
Show the solution with explanations
Keep a running sum, and count each 0 as −1. If you saw the same sum before at index j, the part after j has sum 0.
function findMaxLength(nums) { const first = new Map([[0, -1]]); // sum 0 "seen" just before index 0 let sum = 0, best = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i] === 1 ? 1 : -1; if (first.has(sum)) best = Math.max(best, i - first.get(sum)); else first.set(sum, i); // keep only the earliest index } return best;}console.log(findMaxLength([0, 1])); // 2console.log(findMaxLength([0, 1, 0])); // 2console.log(findMaxLength([0, 0, 1, 0, 0, 0, 1, 1])); // 6| i | value as ±1 | sum | first seen | length |
|---|---|---|---|---|
| 0 | −1 | |||
| 0 | −1 | −1 | new → 0 | |
| 1 | +1 | 0 | at −1 | 1 − (−1) = 2 |
| 2 | −1 | −1 | at 0 | 2 − 0 = 2 |
There are two changes from Question 5. First, store the first index (not a count). Second, change the values (0 becomes −1). It takes O(n) time and O(n) space. (LeetCode 525.)
Return the number of non-empty subarrays whose sum is divisible by k.
Hint 1
Hint 2
-7 % 5 is -2 (a negative remainder). So you must change it to a non-negative one.Show the solution with explanations
This is like Question 5, but the Map key is the remainder sum mod k, made non-negative.
function subarraysDivByK(nums, k) { const seen = new Map([[0, 1]]); let sum = 0, count = 0; for (const x of nums) { sum += x; const r = ((sum % k) + k) % k; // always 0..k-1, even for negative sums count += seen.get(r) ?? 0; seen.set(r, (seen.get(r) ?? 0) + 1); } return count;}console.log(subarraysDivByK([4, 5, 0, -2, -3, 1], 5)); // 7console.log(subarraysDivByK([5], 9)); // 0O(n) time, O(k) space. Without the + k fix, the remainders −2 and 3 would count as different, but they mean the same thing when k = 5. The answer would be wrong.
This problem joins prefix sums with modular arithmetic (working with remainders). It uses two earlier lessons together. (LeetCode 974.)
Make it stick
- Build the prefix array for [2, 5, 1, 3] and use it to find sum(1..2).
- Write the range formula and explain the leading 0.
- Explain product-except-self with a left pass and a right pass.
- Write subarray-sum-equals-k from memory, including the starting Map entry.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
Lesson 21 covers two pointers. You use two indices that move through the array together. They can start at both ends and move towards the middle, or they can move in the same direction. With them you can solve pair sums, 3Sum and partitioning in a single pass.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series