← Learn DSA · Lesson 2 of 11
Sliding Window
Reuse the previous window instead of recomputing it.
The idea
A sliding window is the specialisation of two pointers for problems about contiguous runs. Both indices move forward; the span between them is the window.
The insight is subtraction. Moving a window one step right adds one element and removes one — everything else is unchanged. Recomputing the whole window each time throws away that overlap and turns O(n) into O(n·k).
Two variants:
- Fixed size. The window is always k wide. Add the entering element, subtract the leaving one.
- Variable size. The window grows from the right until it violates a
condition, then shrinks from the left until it is valid again. Each index
enters once and leaves once, so it is still linear despite the nested
while.
The variable form is where people misjudge the complexity. The inner loop looks quadratic, but the left edge only ever moves forward — it cannot do more total work than the right edge did.
Walkthrough
A fixed window of three sliding right. Each step reads one element entering and one leaving — never the whole window.
What it costs
- time
- O(n)
- space
- O(1) for a fixed window, O(k) when tracking window contents
Both edges only move forward, so each index is handled at most twice however deeply nested the loops look.
When to reach for it
- The problem says contiguous, consecutive, or substring.
- You want the longest, shortest, or best run satisfying some condition.
- A fixed length k appears in the statement.
- Recomputing each candidate range would repeat most of the previous one.
Rather than the obvious alternative
Prefix sums
Prefix sums answer arbitrary ranges in any order; a window answers ranges that slide, in O(1) space. Use the window when the range moves, prefix sums when queries land anywhere.
A nested loop
The direct trade. Recomputing the window each step is O(n·k); adding one element and removing one is O(1).
How to spot it
- The problem says 'contiguous', 'consecutive', or 'substring'.
- You are asked for a longest, shortest, or best run satisfying a condition.
- A fixed length k appears in the statement.
- Recomputing each candidate range would repeat most of the previous one.
Where it goes wrong
Recomputing the window
Summing the whole window on every step is the mistake the technique exists to remove. Add and subtract instead.
Shrinking with `if` instead of `while`
One violation can require removing several elements. An `if` fixes it once and leaves the window invalid.
Measuring the window wrong
The size is `right - left + 1`. Forgetting the `+ 1` is the most common off-by-one here.