Sliding Window
Sliding window maintains a contiguous segment (a subarray or substring) and slides it along the data, updating its state in O(1) per step instead of recomputing everything from scratch.
There are two kinds: a fixed-size window of length k, and a flexible window that resizes by a condition (expand on the right, shrink on the left when it is violated). The key to O(n) is that each element enters and leaves the window at most once.
Imagine sitting on a coach looking out the window.
- The window always shows exactly K meters of road, and as the bus moves the frame slides along with it.
- You don't have to look back at the last kilometer — only at the current window.
How to spot it
When you see these cues in the problem, reach for Sliding Window
| Keyword in the problem | Why it points to this topic |
|---|---|
| contiguous subarray | Fixed or variable-size subarray / substring |
| sum / max / min of K | Fixed window of K elements |
| longest substring meeting a condition | Window grows and shrinks under a constraint |
| window without duplicates | Set tracks characters currently in the window |
When to use
3 typical situations where this topic applies
You need to go through every contiguous segment of length K in an array/string
Computing the max/min/sum of fixed segments, or of segments that meet a condition
Avoiding recomputation from scratch each time (O(n·k) → O(n))
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
The problem needs non-contiguous sequences (subsequences): it is not Sliding Window
The window condition is not monotone in size: resizing goes wrong → go back to brute force or DP
You need to access elements outside the window: Sliding Window loses its O(n) property
Illustration
Edit the data, then press Play to see each step.
// Largest sum of any K consecutive elementslet windowSum = 0, maxSum = 0for (let r = 0; r < k; r++) windowSum += nums[r] // build initialmaxSum = windowSum // first windowfor (let r = k; r < nums.length; r++) { // slide windowSum += nums[r] - nums[r - k] maxSum = Math.max(maxSum, windowSum)}Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function slidingWindow(nums: T[], k: number): R {
let left = 0
let windowState = initState()
let answer = initAnswer()
for (let right = 0; right < nums.length; right++) {
// 1. Expand: include nums[right] in windowState
expand(windowState, nums[right])
// 2. Shrink while the window violates the constraint
while (!isValid(windowState)) {
shrink(windowState, nums[left])
left++
}
// 3. Update the answer based on the valid window
answer = best(answer, windowState)
}
return answer
}Recap
A quick summary — reread it before your interview
Key points
Maintain 2 pointers left and right that form the window
When expanding: advance right, update the state
When shrinking: advance left, remove the element from the state
Each element is visited at most 2 times → O(n)
Common mistakes
Forgetting to update the state when shrinking the window (removing the left element from the count/sum)
Using
ifinstead ofwhilewhen shrinking a variable window — you must keep shrinking until the window is validUsing a fixed window when the problem actually needs a variable one (and vice versa)
Complexity
Time O(n), Space O(1) hoặc O(k) tuỳ trạng thái lưu trữPractice problems for this topic
Grouped by difficulty — work through them in order to build confidence