Sliding Window: Fixed Size

Every block of k items

Many problems ask about every window. A window is a block of k items that sit next to each other in an array or a string. Examples: the largest sum of 3 days in a row, the average of every 5 readings, or the most vowels in any 4 letters in a row. An array of n items has n − k + 1 such windows.

The brute force repeats work

Computing each window from scratch costs k steps per window:

function maxSumBrute(nums, k) {  let best = -Infinity;  for (let start = 0; start + k <= nums.length; start++) {    let sum = 0;    for (let i = start; i < start + k; i++) sum += nums[i];   // k steps, every time    best = Math.max(best, sum);  }  return best;}console.log(maxSumBrute([2, 1, 5, 1, 3, 2], 3)); // 9

That costs O(n × k) steps. With n = 10⁵ and k = 5 × 10⁴, it is billions of steps. But two windows that sit next to each other share k − 1 items. Adding those items again and again is wasted work. Lesson 11 told us to look for this kind of waste.

Slide: add one, remove one

When the window moves one step to the right, only two items change. One item enters on the right and one item leaves on the left. So do not add everything again. Just update the sum:

Traced: largest sum of 3 neighbours

1const nums = [2, 1, 5, 1, 3, 2];2const k = 3;▶let sum = nums[0] + nums[1] + nums[2];4let best = sum;5for (let i = k; i < nums.length; i++) {6  sum += nums[i] - nums[i - k];7  best = Math.max(best, sum);8}9console.log(best);

The fixed-window template

You do not need to build the first window separately. Walk through the array once. At each index, add the item that enters. Remove the item that leaves, but only once the window is full. Use the window when it is complete:

function fixedWindow(nums, k) {  let state = 0;                         // e.g. a sum or a count  let best = -Infinity;  for (let i = 0; i < nums.length; i++) {    state += nums[i];                    // 1. add the item entering on the right    if (i >= k) state -= nums[i - k];    // 2. remove the item that fell off the left    if (i >= k - 1) {                    // 3. a full window ends at i: use it      best = Math.max(best, state);    }  }  return best;}console.log(fixedWindow([2, 1, 5, 1, 3, 2], 3)); // 9

The three numbered steps are the whole pattern. Only the state changes from problem to problem. The state is the information you keep about the window, such as a sum, a count, or a frequency map (a Map that counts each value). Check the two conditions with care. i >= k means “an item must leave”. i >= k - 1 means “a full window exists”. These are the places where off-by-one mistakes (being wrong by exactly one) usually happen.

Averages of every window

A moving average is the average of the last k values, and it updates as the window moves. People use it for prices or sensor readings. It is the window sum divided by k:

function windowAverages(nums, k) {  const out = [];  let sum = 0;  for (let i = 0; i < nums.length; i++) {    sum += nums[i];    if (i >= k) sum -= nums[i - k];    if (i >= k - 1) out.push(sum / k);  }  return out;}console.log(windowAverages([1, 3, 2, 6, -1, 4, 1, 8, 2], 5)); // [ 2.2, 2.8, 2.4, 3.6, 2.8 ]

Counting inside a window

The state can be a count instead of a sum. In this example we find the most vowels (a, e, i, o, u) in any k letters in a row.

function maxVowels(s, k) {  const isVowel = (ch) => "aeiou".includes(ch);  let count = 0, best = 0;  for (let i = 0; i < s.length; i++) {    if (isVowel(s[i])) count++;                     // entering    if (i >= k && isVowel(s[i - k])) count--;       // leaving    if (i >= k - 1) best = Math.max(best, count);  }  return best;}console.log(maxVowels("abciiidef", 3)); // 3   ("iii")

A window with a frequency map

Sometimes the question is about which values are in the window. For example: how many distinct (different) values, anagrams, or duplicates. Then the state is a frequency map (Lesson 15). A frequency map is a Map that stores how many times each value appears. Add one to the count of the value that enters. Subtract one from the count of the value that leaves. Delete a key when its count reaches 0. This keeps freq.size equal to the number of distinct values.

function distinctInWindows(nums, k) {  const freq = new Map();  const out = [];  for (let i = 0; i < nums.length; i++) {    freq.set(nums[i], (freq.get(nums[i]) ?? 0) + 1);       // add the new item    if (i >= k) {      const old = nums[i - k];      freq.set(old, freq.get(old) - 1);                    // remove the old item      if (freq.get(old) === 0) freq.delete(old);           // keep size = distinct count    }    if (i >= k - 1) out.push(freq.size);  }  return out;}console.log(distinctInWindows([1, 2, 1, 3, 4, 2, 3], 4)); // [ 3, 4, 4, 3 ]

Practice questions

For each question, first decide what the window state is (a sum, a count or a map). Then fill in the template.

function findMaxAverage(nums, k) {  let sum = 0, best = -Infinity;  for (let i = 0; i < nums.length; i++) {    sum += nums[i];    if (i >= k) sum -= nums[i - k];    if (i >= k - 1) best = Math.max(best, sum);  }  return best / k;}console.log(findMaxAverage([1, 12, -5, -6, 50, 3], 4)); // 12.75console.log(findMaxAverage([5], 1));                    // 5

function maxVowels(s, k) {  const vowels = new Set("aeiou");  let count = 0, best = 0;  for (let i = 0; i < s.length; i++) {    if (vowels.has(s[i])) count++;    if (i >= k && vowels.has(s[i - k])) count--;    if (i >= k - 1) best = Math.max(best, count);    if (best === k) break;                 // cannot do better than all vowels  }  return best;}console.log(maxVowels("abciiidef", 3)); // 3console.log(maxVowels("leetcode", 3));  // 2console.log(maxVowels("rhythms", 4));   // 0

function numOfSubarrays(arr, k, threshold) {  const need = k * threshold;  let sum = 0, count = 0;  for (let i = 0; i < arr.length; i++) {    sum += arr[i];    if (i >= k) sum -= arr[i - k];    if (i >= k - 1 && sum >= need) count++;  }  return count;}console.log(numOfSubarrays([2, 2, 2, 2, 5, 5, 5, 8], 3, 4)); // 3

function getAverages(nums, k) {  const size = 2 * k + 1;  const out = new Array(nums.length).fill(-1);  let sum = 0;  for (let i = 0; i < nums.length; i++) {    sum += nums[i];    if (i >= size) sum -= nums[i - size];    if (i >= size - 1) out[i - k] = Math.floor(sum / size);  }  return out;}console.log(getAverages([7, 4, 3, 9, 1, 8, 5, 2, 6], 3)); // [ -1, -1, -1, 5, 4, 4, -1, -1, -1 ]console.log(getAverages([100000], 0));                    // [ 100000 ]

function maxSatisfied(customers, grumpy, minutes) {  let base = 0;  for (let i = 0; i < customers.length; i++) {    if (grumpy[i] === 0) base += customers[i];  }  let gain = 0, bestGain = 0;  for (let i = 0; i < customers.length; i++) {    if (grumpy[i] === 1) gain += customers[i];    if (i >= minutes && grumpy[i - minutes] === 1) gain -= customers[i - minutes];    bestGain = Math.max(bestGain, gain);  }  return base + bestGain;}console.log(maxSatisfied([1, 0, 1, 2, 1, 1, 7, 5], [0, 1, 0, 1, 0, 1, 0, 1], 3)); // 16

function containsNearbyDuplicate(nums, k) {  const window = new Set();  for (let i = 0; i < nums.length; i++) {    if (window.has(nums[i])) return true;    window.add(nums[i]);    if (i >= k) window.delete(nums[i - k]);    // keep only the last k values  }  return false;}console.log(containsNearbyDuplicate([1, 2, 3, 1], 3));       // trueconsole.log(containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2)); // false

Make it stick

What's next

In this lesson the window size was fixed. In Lesson 23 the window grows and shrinks. It gets bigger while a rule is true, and it gets smaller when the rule breaks. This is the technique behind “longest substring without repeating characters” and many other popular problems.