Sliding Window
A contiguous range that grows on the right and shrinks on the left while a condition holds.
Newinterview weight 8012 problems2 visualisers
18
mastery
Attempts logged
0
Predicted success on the next one
33%
Solved here
0 / 12
What you actually need to hold in your head
- Fixed size versus variable size windows
- Shrink while invalid, record while valid
- Monotonic deque for window extrema
- At most K minus at most K-1 gives exactly K
Comfortable with these first
Next in the path
Prefix Sum
Watch it run
Step through the algorithm before you write it.
Patterns in this topic
The trigger phrases are what you are training yourself to notice.
Fixed Sliding WindowO(n) time, O(1) or O(alphabet) space
Compute the first window, then for every step add the entering element and remove the leaving one instead of recomputing.
subarray of size kmax average of k elements
Variable Sliding WindowO(n), each index enters and leaves once
Expand the right edge greedily. While the window violates the constraint, shrink from the left. Record the answer whenever the window is valid.
longest substring with conditionsmallest subarray with sum at least X
Monotonic DequeO(n)
A deque holding indices in decreasing value order. The front is always the window maximum.
sliding window maximumconstrained subsequence sum
Sliding Window problems
Ordered by sheet phase, so the early ones are the highest signal.
0 / 12 solved