Recomputing a window from scratch is wasteful — it only changed at the edges. Add what enters, subtract what leaves, and an O(n·k) scan becomes O(n).
Controls
window size k3
target15
The Window
step 0
window
–
current
0
best
–
Insight
When a window slides by one, only two elements change. Update the running value instead of recomputing it and each step becomes O(1).
operations0
naive cost0
Complexity
Sliding windowO(n)
Naive recomputeO(n·k)
SpaceO(1) / O(k)
Sliding Window
Stop recomputing what barely changed.
Quick Context
The sliding window technique maintains a contiguous range over an array or string and moves it along, updating a running summary incrementally rather than rebuilding it. It turns O(n·k) into O(n).
Fixed Windows: Add One, Remove One
To find the maximum sum of k consecutive elements, the naive approach sums every window from scratch — k additions per position, O(n·k) overall.
But sliding from position i to i+1 only removes one element and adds one:
window_sum = window_sum - a[i] + a[i + k]
Two operations instead of k, no matter how large k is. Compare the operation counters as you raise k — the sliding window's count does not move.
Variable Windows: Grow and Shrink
Harder problems let the window change size. The pattern is always the same:
Expand the right edge until the window satisfies (or violates) some condition.
Contract the left edge while the condition still holds, recording the best answer.
Both pointers only ever move forward, so although the code contains nested loops, each element is added once and removed once — total work is still O(n). That amortised argument is the part people find surprising.
Longest Substring Without Repeats
Expand right, adding characters to a set. If the new character is already inside, contract from the left until it is not. Record the longest window seen.
Step through it and watch the left edge jump forward exactly when a duplicate appears — never scanning backwards, never recomputing the set from scratch.
How to Spot One
Reach for a sliding window when the problem asks about a contiguous subarray or substring, and phrases it as longest/shortest/maximum/minimum satisfying a condition.
The critical requirement is that the running summary can be updated incrementally. Sums and counts work. If the condition needs the whole window recomputed — a median, say — you need a heavier structure such as a heap or balanced tree alongside the window.
Interactive Exploration Guide
Run max-sum with k = 3. Watch each slide subtract one value and add one — two operations, never three.
Raise k to 5. The naive cost climbs while the sliding-window operation count stays flat. That is the whole point.
Switch to shortest subarray ≥ target. The window now grows and shrinks; note that both edges only move rightward.
Run longest substring without repeats. The left edge jumps forward only when a duplicate is found.
Count total pointer movements. Each index is entered once and left once — that is why nested loops still give O(n).
Key Takeaway
A sliding window keeps a running summary and updates it at the edges instead of rebuilding it. Fixed windows add-and-remove; variable windows expand and contract. Because both pointers only move forward, the total cost stays linear even when the code looks nested.
Cheat sheet
Sliding Window
Recomputing a window from scratch is wasteful — it only changed at the edges. Add what enters, subtract what leaves, and an O(n·k) scan becomes O(n).