ENDEAR
Start free
algorithmfree

Sliding window

Find the largest sum of k consecutive numbers without re-adding the whole window each time.

time
O(n)
space
O(1)

// step through it

step 1 / 9
1function maxWindowSum(nums, k) {2  let total = 0;3  for (let i = 0; i < k; i++) total += nums[i];4  let best = total;5  for (let i = k; i < nums.length; i++) {6    total += nums[i] - nums[i - k];7    best = Math.max(best, total);8  }9  return best;10}
k
= 3
total
= 8
  1. 2
  2. 1
  3. 5
  4. 1
  5. 3
  6. 2

Add up the first window of k = 3 numbers: total = 8.

How it works

Sum the first k numbers once. Then slide the window one step at a time: add the number that enters on the right and subtract the one that leaves on the left. Each window costs O(1) to update, so the whole scan is linear.