The problem it solves
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:
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.
A window that grows and shrinks
The sliding window technique handles problems about contiguous subarrays or substrings. Instead of examining every possible window — O(n²) of them — it maintains one window with two pointers and adjusts it in a single pass.
Two variants, and knowing which you need is most of the work.
Fixed size. The window is always k wide. Slide it forward, adding the new element and removing the old one:
def max_sum_k(arr, k):
window = sum(arr[:k])
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k] # add new, remove old - O(1) per step
best = max(best, window)
return best
Recomputing the sum for each window would be O(nk). Updating incrementally makes it O(n), and that incremental update is the whole idea.
Variable size. The window grows while a condition holds and shrinks when it is violated:
def longest_unique(s):
seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1 # shrink past the duplicate
seen[ch] = right
best = max(best, right - left + 1)
return best
The pattern is: expand right unconditionally, and move left only as far as needed to restore validity. Each pointer moves at most n times in total, so the whole scan is O(n) despite the nested appearance.
Recognising the shape
The signals are consistent:
- The problem mentions a contiguous subarray, substring or run.
- It asks for the longest, shortest, or a count of windows satisfying a condition.
- The condition can be updated incrementally as elements enter and leave.
That third point is the real constraint. Sliding window works when adding and removing an element is cheap. Sum, count, and character frequencies all qualify. "Contains a specific permutation" does after being expressed as a frequency comparison. "The subarray's median" does not, cheaply.
| Problem | Window type | Condition |
|---|
| Max sum of k elements | Fixed | — |
| Longest substring without repeats | Variable | All characters distinct |
| Smallest subarray with sum ≥ target | Variable | Running sum ≥ target |
| Longest substring with at most k distinct | Variable | Distinct count ≤ k |
| Anagram or permutation in a string | Fixed | Frequency map matches |
| Max of every k-window | Fixed | Needs a monotonic deque |
The template worth memorising
Most variable-window problems fit one shape:
def sliding_window(arr):
left = 0
state = init_state()
best = 0
for right in range(len(arr)):
add(state, arr[right]) # expand
while not valid(state): # shrink until valid again
remove(state, arr[left])
left += 1
best = max(best, right - left + 1) # record
return best
Two variants of the middle block distinguish the two families of question:
Longest valid window: shrink only while invalid, and record after shrinking — as above.
Shortest valid window: shrink while still valid, recording before each shrink, because the goal is the smallest window that satisfies the condition.
Getting that inversion wrong is the most common sliding-window bug, and the symptom is an answer that is consistently too long or too short.
Recomputing versus updating, and the bug that hides in the shrink
A sliding window turns a nested loop into a single pass by updating a running answer instead of rebuilding it. The fixed-size version is easy. The variable-size one has a subtlety in when you shrink, and getting it wrong produces answers that are almost right.
Try it yourself
- 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).
Where that leaves you
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.
The monotonic deque variant
One family needs more than a running counter: the maximum of every k-length window.
Recomputing the maximum per window is O(nk). A heap gives O(n log k). A monotonic deque gives O(n).
The deque holds indices whose values are in decreasing order. Before appending a new index, pop everything smaller from the back — those can never be the maximum again, because the new element is larger and stays in the window longer. Pop from the front when it falls out of the window.
from collections import deque
def max_sliding_window(arr, k):
dq, out = deque(), []
for i, x in enumerate(arr):
while dq and arr[dq[-1]] <= x:
dq.pop() # smaller values can never win
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # out of the window
if i >= k - 1:
out.append(arr[dq[0]]) # front is the maximum
return out
Each index is pushed and popped at most once, so it is O(n) despite the inner while. The front of the deque is always the current window's maximum.
This structure generalises: the same idea supports minimum-in-window, and it appears inside some dynamic programming optimisations.
Where it is used
- Rate limiting. Requests in the last 60 seconds is a sliding window over timestamps.
- Streaming statistics. Moving averages, rolling maxima, and any windowed aggregate over a data stream.
- Network protocols. TCP's sliding window controls how much unacknowledged data may be in flight.
- Time-series features. Rolling means and standard deviations for forecasting models.
- Text processing. Finding substrings with given character properties; n-gram extraction.
- Anomaly detection. Comparing a recent window against a baseline.
The rate-limiting case is worth noting as the everyday production use: a sliding window log or counter is how APIs enforce quotas, and the fixed-window alternative allows twice the intended rate at the boundary between windows.
Common mistakes
- Shrinking in the wrong condition — the longest/shortest inversion described above.
- Recording the answer at the wrong point, before rather than after restoring validity.
- Not removing from the state when shrinking, so counts drift.
- Using it on non-contiguous problems. Sliding window is only for runs; subsequences need dynamic programming.
- Recomputing the aggregate from scratch, which discards the entire advantage.
- Off-by-one in the window size: the width is
right - left + 1.
Questions people ask
Fixed or variable window? Fixed when the problem states a size k; variable when it asks for the longest or shortest window satisfying a condition.
Is it always O(n)? Yes when each pointer only moves forward and the state update is O(1). Both pointers traverse the array at most once.
How is it different from two pointers? It is a two-pointer technique, specialised to contiguous ranges with a maintained condition.
Can it handle negative numbers? For sum-based conditions, not straightforwardly — the running sum is no longer monotonic as the window grows. Prefix sums plus a hash map is the usual alternative.
What about subsequences rather than subarrays? Not applicable — subsequences are not contiguous. That is dynamic programming territory.
Why a deque for window maximum? Because it discards elements that can never win, giving amortised O(1) per element rather than a heap's O(log k).
Recap in one screen
- One window with two forward-moving pointers replaces examining every subarray.
- Fixed windows update incrementally: add the entering element, remove the leaving one.
- Variable windows expand always and shrink only to restore validity — and the longest/shortest cases shrink under opposite conditions.
- Only works when the condition can be updated cheaply as elements enter and leave, and only for contiguous ranges.
- A monotonic deque gives window maximum in O(n), where a heap would give O(n log k).