Visualized DSA Strategies

Episode 5 Sliding Window

1 h 0 min · Go · Quiz

Title card of Episode 5: Sliding Window

▶ This video is coming to YouTube soon.

The complete guide to the sliding window, in Go. First the theory: what a window is, fixed vs variable windows, the two templates in Go (range over the slice, and a for with only a condition as Go's while), what the window remembers in Go (a running sum, a map[int]bool as the set, a map of counts with delete when a count reaches zero, and a slice of indices as the deque), and why a loop inside a loop is still O(n). Then nine types of window, each worked as a small problem in full: examples, the brute force animated beside the running line of code, the complete code, every line explained, and the sliding window solution the same way.

What you'll learn

  • What a window is, and fixed vs variable windows
  • The fixed and variable window templates in Go, line by line
  • Why each number entering once and leaving once makes it O(n)
  • Fixed windows: a running sum and a running count
  • Variable windows: the longest that obeys a rule, with a sum or a map[int]bool as a set
  • The shortest window: shrink while it's still valid, with math.MaxInt as nothing found
  • At most k kinds with a map of counts and delete, and counting every valid window
  • Exactly k = at most k − at most k−1
  • The window maximum with a monotonic deque built on a Go slice

Chapters

  1. 0:00Intro
  2. 0:17What's a window?
  3. 0:44Fixed vs variable windows
  4. 1:11The fixed window template
  5. 1:59The variable window template
  6. 2:54Why it's O(n)
  7. 3:21What the window remembers
  8. 4:16Nine kinds of window
  9. 4:58Type 1 · Best sum of k in a row
  10. 10:52Type 2 · Most vowels in k letters
  11. 16:45Type 3 · Longest run with sum ≤ k
  12. 22:20Type 4 · Longest run with no repeated number
  13. 28:08Type 5 · Shortest run with sum ≥ target
  14. 33:56Type 6 · Longest run with at most 2 different numbers
  15. 39:51Type 7 · How many runs have sum ≤ k?
  16. 45:43Type 8 · Runs with exactly 2 odd numbers
  17. 51:38Type 9 · Max of every window of size k
  18. 57:59Spot the pattern
  19. 58:31Quiz: which window?
  20. 59:09Recap

Quiz: test yourself

The 4 questions from the end of the episode. Pick an answer to see why it's right.