Episode 5 Sliding Window

What you'll learn

• What a window is, and fixed vs variable windows
• The fixed and variable window templates, 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 set
• The shortest window: shrink while it's still valid
• At most k kinds with a map, and counting every valid window
• Exactly k = at most k − at most k−1
• The window maximum with a monotonic deque

Chapters

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