Array patterns · Lesson 8 of 23

Prefix sums

Any range sum in O(1) after O(n) preparation, plus a hash map to count subarrays.

11 minutes2 games

If you'll often ask "what's the sum from i to j?", don't add it up each time. Build prefix where prefix[k] = the sum of the first k elements. Then:

sum(i..j) = prefix[j + 1] - prefix[i]

O(n) once to prepare, then O(1) per question.

k	0	1	2	3	4	5
nums[k]	3	1	4	1	5	—
prefix[k]	0	3	4	8	9	14

The sum of nums[1..3] = 1 + 4 + 1 = prefix[4] - prefix[1] = 9 − 3 = 6.

JavaScript

const nums = [3, 1, 4, 1, 5]
const prefix = [0]
for (const x of nums) prefix.push(prefix[prefix.length - 1] + x)

const rangeSum = (i, j) => prefix[j + 1] - prefix[i]
console.log(prefix)
console.log(rangeSum(1, 3), rangeSum(0, 4), rangeSum(2, 2))

Counting subarrays that sum to k

The key trick: the part from i to j sums to k when prefix[j+1] - prefix[i] = k, i.e. prefix[i] = prefix[j+1] - k. So as we go, keep a hash map of how many times each prefix appeared, and at each position ask how many times we've seen current - k. Unlike a sliding window, this works with negative numbers.

JavaScript

function countSubarrays(nums, k) {
  const seen = new Map([[0, 1]])   // the empty prefix
  let current = 0, count = 0
  for (const x of nums) {
    current += x
    count += seen.get(current - k) || 0
    seen.set(current, (seen.get(current) || 0) + 1)
  }
  return count
}

console.log(countSubarrays([1, 1, 1], 2), countSubarrays([1, -1, 1, -1], 0))

Quick question

prefix = [0, 2, 5, 9, 10]. What's the sum of nums[1..2]?

Exercise

Write pivotIndex(nums): the first index where the sum to its left equals the sum to its right, or -1. It must print 3 -1.

Expected output: 3 -1

JavaScript

function pivotIndex(nums) {
  
}

console.log(pivotIndex([1, 7, 3, 6, 5, 6]), pivotIndex([1, 2, 3]))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 2 games

DSA

Array patterns · Lesson 8 of 23

Prefix sums

Any range sum in O(1) after O(n) preparation, plus a hash map to count subarrays.

11 minutes2 games

If you'll often ask "what's the sum from i to j?", don't add it up each time. Build prefix where prefix[k] = the sum of the first k elements. Then:

sum(i..j) = prefix[j + 1] - prefix[i]

O(n) once to prepare, then O(1) per question.

k	0	1	2	3	4	5
nums[k]	3	1	4	1	5	—
prefix[k]	0	3	4	8	9	14

The sum of nums[1..3] = 1 + 4 + 1 = prefix[4] - prefix[1] = 9 − 3 = 6.

JavaScript

const nums = [3, 1, 4, 1, 5]
const prefix = [0]
for (const x of nums) prefix.push(prefix[prefix.length - 1] + x)

const rangeSum = (i, j) => prefix[j + 1] - prefix[i]
console.log(prefix)
console.log(rangeSum(1, 3), rangeSum(0, 4), rangeSum(2, 2))

Counting subarrays that sum to k

JavaScript

function countSubarrays(nums, k) {
  const seen = new Map([[0, 1]])   // the empty prefix
  let current = 0, count = 0
  for (const x of nums) {
    current += x
    count += seen.get(current - k) || 0
    seen.set(current, (seen.get(current) || 0) + 1)
  }
  return count
}

console.log(countSubarrays([1, 1, 1], 2), countSubarrays([1, -1, 1, -1], 0))

Quick question

prefix = [0, 2, 5, 9, 10]. What's the sum of nums[1..2]?

Exercise

Write pivotIndex(nums): the first index where the sum to its left equals the sum to its right, or -1. It must print 3 -1.

Expected output: 3 -1

JavaScript

function pivotIndex(nums) {
  
}

console.log(pivotIndex([1, 7, 3, 6, 5, 6]), pivotIndex([1, 2, 3]))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 2 games