Sliding Window
Fixed and variable windows, have/need counters and counting tricks.
5 notes · 24 min total
Questions0 of 29 done
Patterns
- 1Fixed-Size WindowSlide a window of exactly k items across an array in O(n), updating only the two elements at its edges.6 min
- 2Longest Valid WindowGrow the window greedily, shrink it with a while loop when a rule breaks, and record the longest valid stretch in O(n).6 min
- 3Minimum Window (Have/Need)Find the shortest window that satisfies a rule by shrinking while it stays valid, using have/need counters for character quotas.4 min
- 4Inverse Window (Pick from the Ends)When you must take items from the left or right end, slide a window over the middle part you keep instead.4 min
- 5Counting Subarrays: atMost(k) − atMost(k−1)Count valid subarrays by adding the window length at each step, and get exactly k as atMost(k) minus atMost(k-1).4 min