Sliding Window
Process every contiguous range of an array or string in one pass.
5 pages, free to read
- 1
Fixed-size window
BeginnerWhen a problem asks about every block of exactly k consecutive elements, keep one running answer and update it as the block slides by one, instead of recomputing each block from scratch.
8 min read - 2
Variable-size window
IntermediateGrow the window with a right pointer and shrink it with a left pointer only when needed, so you find the shortest or longest valid subarray in one O(n) pass.
10 min read - 3
Windows with a hash map
IntermediateWhen validity depends on which characters or values are inside the window, keep their counts in a hash map so each step updates in O(1) and the whole scan stays O(n).
11 min read - 4
Sliding maximum with a deque
AdvancedKeep a double-ended queue of indices whose values are decreasing, so the front is always the current window's maximum and every element is pushed and popped at most once: O(n) for all windows.
11 min read - 5
Counting subarrays: the at-most-K trick
AdvancedCounting subarrays with exactly K of something is hard to do with one window, but counting 'at most K' is easy, so compute exactly(K) = atMost(K) - atMost(K - 1).
10 min read