Sliding window

Episode 22 Sliding Window Maximum

6 min · LeetCode 239 · Java

Title card of Episode 22: Sliding Window Maximum

▶ This video is coming to YouTube soon.

LeetCode 239, Sliding Window Maximum, solved on screen. Three examples show the cases: a window of 3 sliding over eight numbers, k = 1 where every number is its own window, and k = n with a single window. The brute force rescans every window for its max, O(n · k). Then a monotonic deque of indices keeps only the numbers that could still be a max, their values falling from front to back, so the front is always the answer: O(n) time, O(k) space.

What you'll learn

  • What Sliding Window Maximum asks, through three worked examples
  • The brute force: rescan every window, O(n · k) time
  • The key idea: a smaller, older number can never be a max again
  • The monotonic deque: O(n) time, O(k) space
  • Why the deque stores indices, not values

Chapters

  1. 0:00The problem
  2. 0:20Examples
  3. 1:00Brute force, visualized
  4. 1:50Brute force: the code
  5. 2:08Brute force, line by line
  6. 2:47Monotonic deque: the idea
  7. 3:11Monotonic deque, visualized
  8. 4:17Monotonic deque: the code
  9. 4:38Monotonic deque, line by line
  10. 5:34Comparing the approaches