Lesson 06 of 2417 min read

Sliding Window

Two pointers with a rule about what is allowed between them. Fixed-size and variable-size windows cover an enormous number of "longest" and "shortest substring" questions.

By the end: Solve any contiguous-subarray question in one pass.

A sliding window is two pointers with a rule about what is allowed between them. The region from left to right is the window; you grow it on the right and shrink it on the left, and you never go backwards.

That "never go backwards" is why it is O(n) even though there is a loop inside a loop: each pointer advances at most n times in total, so the combined work is at most 2n.

Fixed-size windows

The easier case: the window is always k wide. Add the incoming element, remove the outgoing one, and you have the new answer without recomputing anything.

Best sum of any k consecutive elements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function maxSumOfK(nums, k) {
  if (nums.length < k) return null;

  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];    // the first window
  let best = sum;
  const trace = [`window 0..${k - 1} sum ${sum}`];

  for (let right = k; right < nums.length; right++) {
    sum += nums[right] - nums[right - k];        // add the new, drop the old
    trace.push(`window ${right - k + 1}..${right} sum ${sum}`);
    if (sum > best) best = sum;
  }
  return { best, trace };
}

const r = maxSumOfK([2, 1, 5, 1, 3, 2], 3);
console.log('best:', r.best);
r.trace.forEach(t => console.log('  ' + t));

Output

Notice what did not happen: we never re-added the same element twice. The naive version recomputes each window from scratch, which is O(n × k).

The saving, measured

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function naive(nums, k) {
  let ops = 0, best = -Infinity;
  for (let i = 0; i + k <= nums.length; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) { sum += nums[j]; ops++; }
    best = Math.max(best, sum);
  }
  return { best, ops };
}

function windowed(nums, k) {
  let ops = 0, sum = 0;
  for (let i = 0; i < k; i++) { sum += nums[i]; ops++; }
  let best = sum;
  for (let r = k; r < nums.length; r++) { sum += nums[r] - nums[r - k]; ops++; best = Math.max(best, sum); }
  return { best, ops };
}


const data = Array.from({ length: 1000 }, (_, i) => (i * 37) % 100);
console.log('naive  k=100:', naive(data, 100));
console.log('window k=100:', windowed(data, 100));

Output

Variable-size windows: the template

This is the shape that matters. The window grows until it breaks a rule, then shrinks until it is valid again. Write it once and you will recognise it forever.

The template. Memorise this shape.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16let left = 0;
let best = 0;
// some state describing the window: a count, a sum, a Map...

for (let right = 0; right < arr.length; right++) {
  // 1. ADD arr[right] to the window state.

  while (/* the window is invalid */) {
    // 2. REMOVE arr[left] from the window state, then left++.
  }

  // 3. The window is now valid. Record the answer.
  best = Math.max(best, right - left + 1);
}

return best;

Longest substring without repeating characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24function longestUnique(s) {
  const lastSeen = new Map();      // char → its most recent index
  let left = 0, best = 0, bestStr = '';

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // If we have seen this character inside the current window, jump left
    // past its previous position. Never move left backwards.
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, right);

    if (right - left + 1 > best) {
      best = right - left + 1;
      bestStr = s.slice(left, right + 1);
    }
  }
  return { best, bestStr };
}

for (const s of ['abcabcbb', 'bbbbb', 'pwwkew', '', 'dvdf']) {
  console.log(JSON.stringify(s).padEnd(11), longestUnique(s));
}

Output

Longest substring with at most k distinct characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function longestWithKDistinct(s, k) {
  const counts = new Map();
  let left = 0, best = 0;

  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);

    while (counts.size > k) {                 // invalid: too many distinct
      const out = s[left];
      counts.set(out, counts.get(out) - 1);
      if (counts.get(out) === 0) counts.delete(out);   // must delete, not just zero
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log('eceba, k=2:', longestWithKDistinct('eceba', 2));      // 3, "ece"
console.log('aa, k=1:   ', longestWithKDistinct('aa', 1));         // 2
console.log('abcdef, k=3:', longestWithKDistinct('abcdef', 3));    // 3

Output

Shortest, not longest

Same template, one difference: record the answer inside the shrink loop, because that is where valid windows are at their smallest.

Shortest subarray with a sum of at least target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function shortestAtLeast(nums, target) {
  let left = 0, sum = 0, best = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    // While the window is VALID, record it and try to shrink further.
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

console.log(shortestAtLeast([2, 3, 1, 2, 4, 3], 7));   // 2, the [4,3]
console.log(shortestAtLeast([1, 4, 4], 4));            // 1
console.log(shortestAtLeast([1, 1, 1, 1], 11));        // 0, impossible

Output

Windows that count instead of measuring

Number of substrings, and the at-most trick

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// Count subarrays with product strictly less than k.
// Each valid window ending at `right` contributes (right - left + 1) subarrays.
function countSubarraysProductLessThan(nums, k) {
  if (k <= 1) return 0;
  let left = 0, product = 1, count = 0;
  for (let right = 0; right < nums.length; right++) {
    product *= nums[right];
    while (product >= k) { product /= nums[left]; left++; }
    count += right - left + 1;
  }
  return count;
}
console.log(countSubarraysProductLessThan([10, 5, 2, 6], 100));   // 8

// "Exactly k" is usually atMost(k) - atMost(k-1).
function atMostKDistinct(nums, k) {
  const counts = new Map();
  let left = 0, total = 0;
  for (let right = 0; right < nums.length; right++) {
    counts.set(nums[right], (counts.get(nums[right]) ?? 0) + 1);
    while (counts.size > k) {
      const out = nums[left];
      counts.set(out, counts.get(out) - 1);
      if (counts.get(out) === 0) counts.delete(out);
      left++;
    }
    total += right - left + 1;
  }
  return total;
}
const exactlyK = (nums, k) => atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
console.log('exactly 2 distinct in [1,2,1,2,3]:', exactlyK([1, 2, 1, 2, 3], 2));   // 7

Output

The hardest common one: minimum window substring

Find the shortest substring of s that contains every character of t, counting duplicates. This is a genuine hard problem and it is the template plus one bookkeeping idea: track how many characters are still missing, so validity is a single integer comparison rather than a map comparison.

Minimum window substring

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
33function minWindow(s, t) {
  if (t.length === 0 || s.length < t.length) return '';

  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);

  let missing = t.length;           // total characters still required
  let left = 0, bestLo = 0, bestLen = Infinity;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (need.has(ch)) {
      if (need.get(ch) > 0) missing--;   // this one was actually needed
      need.set(ch, need.get(ch) - 1);    // may go negative: a surplus
    }

    while (missing === 0) {             // valid: shrink to find the smallest
      if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestLo = left; }
      const out = s[left];
      if (need.has(out)) {
        need.set(out, need.get(out) + 1);
        if (need.get(out) > 0) missing++;   // we just gave up a needed one
      }
      left++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestLo, bestLo + bestLen);
}

console.log(JSON.stringify(minWindow('ADOBECODEBANC', 'ABC')));   // "BANC"
console.log(JSON.stringify(minWindow('a', 'a')));                 // "a"
console.log(JSON.stringify(minWindow('a', 'aa')));                // ""
console.log(JSON.stringify(minWindow('bba', 'ab')));              // "ba"

Output

Your turn: three windows

longestOnesAfterFlips(nums, k) — the longest run of 1s you can get by flipping at most k zeroes. Window rule: at most k zeroes inside.
characterReplacement(s, k) — the longest substring where all characters are the same after changing at most k of them. Window is valid when length - countOfMostFrequent <= k.
maxVowels(s, k) — the most vowels in any window of exactly k characters. This one is a fixed window.

Editable. Fill them in, then run.

function longestOnesAfterFlips(nums, k) {
  // count zeroes in the window; shrink while zeroes > k
}

function characterReplacement(s, k) {
  // keep counts; valid while (windowLen - maxCount) <= k
}

function maxVowels(s, k) {
  // fixed window: add s[right], drop s[right-k]
}

console.log(longestOnesAfterFlips([1,1,1,0,0,0,1,1,1,1,0], 2));            // 6
console.log(longestOnesAfterFlips([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3)); // 10
console.log(characterReplacement('ABAB', 2));                               // 4
console.log(characterReplacement('AABABBA', 1));                            // 4
console.log(maxVowels('abciiidef', 3));                                     // 3
console.log(maxVowels('leetcode', 3));                                      // 2

Output

Recap

A sliding window is two pointers that never move backwards, which is why the nested loop is still O(n).
Fixed size: add the entering element, subtract the leaving one, never recompute.
Variable size: grow on the right, shrink on the left while the window is invalid, then record.
Longest records after the shrink loop; shortest records inside it.
When counting distinct items, delete a key at zero; when matching a multiset, let counts go negative and track how many are still missing.

Fixed-size windows

Variable-size windows: the template

Shortest, not longest

Windows that count instead of measuring

The hardest common one: minimum window substring

Your turn: three windows

Recap

New writing, when it lands.