Sliding Window

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A window [left, right] over a contiguous slice plus a tiny summary of it. Each move adds one element and removes one, so the whole scan is O(n).

   #1
2. ↯use it when

   "Contiguous subarray / substring" + longest, shortest, max or min; "of size k"; "at most k"; an anagram or permutation inside a longer string.

   #2
3. { }template

   Fixed: build the first k, then sum += nums[r] - nums[r - k];. The element leaving is always nums[r - k].

   #3
4. { }template

   Variable: for (r…) { add(r); while (invalid) remove(l++); best = max(best, r - l + 1); } — grow, shrink while invalid, record.

   #4
5. O( )cost

   O(n): right moves n times, left at most n times. Space: O(1) for a sum, O(σ) for int[26] / int[128], O(k) for a deque.

   #5
6. !trap

   Negative numbers break sum windows: removing one can raise the sum. Use prefix sums + a HashMap instead.

   #6
7. !trap

   Longest → record after the shrink loop. Shortest → record inside it, before removing nums[left].

   #7
8. !trap

   Shrink with while, not if: one new element can force several removals.

   #8
9. ✦pro tip

   "Exactly k" = atMost(k) - atMost(k - 1). Max or min of every window → a monotonic ArrayDeque of indices.

   #9

Shaky on a card? Open the chapter or flip its recall cards.