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.
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.
example_01.pyPython
def max_sum_naive(a, k):
best, work = None, 0
for i in range(len(a) - k + 1):
s = 0
for j in range(i, i + k):
s += a[j]
work += 1
best = s if best is None else max(best, s)
return best, work
def max_sum_window(a, k):
s, work = 0, 0
for i in range(k):
s += a[i]
work += 1
best = s
for i in range(k, len(a)):
s += a[i] - a[i - k] # one add, one subtract, whatever k is
work += 2
best = max(best, s)
return best, work
import random
a = [random.Random(8).randrange(100) for _ in range(1000)]
print("%6s %14s %16s %10s" % ("k", "naive adds", "window adds", "same answer"))
for k in (3, 10, 100, 500):
n_best, n_work = max_sum_naive(a, k)
w_best, w_work = max_sum_window(a, k)
print("%6d %14d %16d %10s" % (k, n_work, w_work, n_best == w_best))
# The window column does not grow with k at all -- it is 2n - k, so it
# actually falls slightly as the window widens -- while the naive column
# is k times longer for every k. That is the whole
# technique: the overlap between consecutive windows is everything except
# one element at each end, so recomputing it is redundant work.
#
# Now the variable-size version: the longest substring with no repeated
# character. Here the window grows on every step and shrinks only when
# the invariant breaks.
def longest_unique(s, shrink_all=True):
seen = {}
left, best, best_at = 0, 0, (0, 0)
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
if shrink_all:
left = seen[ch] + 1 # jump past the previous copy
else:
left += 1 # BUG: move one step and hope
seen[ch] = right
if right - left + 1 > best:
best = right - left + 1
best_at = (left, right + 1)
return best, s[best_at[0]:best_at[1]]
for text in ("abcabcbb", "bbbbb", "pwwkew", "abba"):
good = longest_unique(text, True)
bad = longest_unique(text, False)
flag = "" if good == bad else " <-- differs"
print()
print("%-10r correct: %d %r one-step shrink: %d %r%s" % (
text, good[0], good[1], bad[0], bad[1], flag))
# Two of the four inputs separate them, and in both the one-step version
# reports a LONGER answer -- "wwke" and "bba", each of which contains the
# repeat it was supposed to exclude. That is the tell: a window bug of
# this kind overreports, because the window it measured was never valid.
#
# The reason is that one step is not always enough. When the duplicate
# sits several positions inside the window, left has to jump past it in
# one move; nudging left by one leaves the earlier copy inside.
#
# The general rule for the variable window: grow unconditionally, and
# shrink until the invariant is restored -- not once, and not by a fixed
# amount. Whenever the shrink is a single step, check whether one step is
# actually enough.
Output
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).
Run it in Python
A fixed window and a variable one. The first shows the recomputation the technique removes; the second grows and shrinks on demand, which is where most of the real problems live.
sliding_window.pyPython 3
# Sliding window: reuse the previous window instead of recomputing it.
# --- 1. fixed size: best sum of k consecutive items ---------------------
def max_sum_naive(a, k):
ops = 0
best = float("-inf")
for i in range(len(a) - k + 1):
total = 0
for j in range(i, i + k): # recompute the whole window
total += a[j]
ops += 1
best = max(best, total)
return best, ops
def max_sum_window(a, k):
ops = 0
total = sum(a[:k])
ops += k
best = total
for i in range(k, len(a)):
total += a[i] - a[i - k] # one add, one subtract. That is all.
ops += 2
print(f" window {a[i-k+1:i+1]} sum={total}")
best = max(best, total)
return best, ops
data = [2, 1, 5, 1, 3, 2, 7, 1]
k = 3
print(f"data {data}, window {k}")
best, ops = max_sum_window(data, k)
print("best:", best)
naive_best, naive_ops = max_sum_naive(data, k)
print(f"operations: window {ops}, recomputing {naive_ops}")
# --- 2. variable size: longest run with no repeated character ----------
def longest_unique(text):
seen = {} # character -> last index it appeared at
start = best = 0
best_text = ""
for i, ch in enumerate(text):
if ch in seen and seen[ch] >= start:
start = seen[ch] + 1 # jump the left edge past the repeat
seen[ch] = i
if i - start + 1 > best:
best = i - start + 1
best_text = text[start:i + 1]
print(f" i={i} {ch!r} window={text[start:i+1]!r}")
return best, best_text
print()
print("longest substring with no repeats, in 'abcabcbb':")
length, text = longest_unique("abcabcbb")
print("best:", length, repr(text))
Output
How the code works
total += a[i] - a[i - k]The whole technique in one line: add what just entered, subtract what just left. The window's value is carried forward rather than rebuilt, turning O(n·k) into O(n).
total = sum(a[:k])The first window still has to be computed the slow way. Every sliding window has this setup step, and it is a common place to get the bounds wrong by one.
if ch in seen and seen[ch] >= start:The second condition is the subtle one. A repeat only matters if it is inside the current window; an older occurrence already fell off the left edge and must be ignored.
start = seen[ch] + 1The left edge jumps straight past the previous occurrence instead of creeping forward one at a time. Both are correct; this one keeps the whole scan linear.
i - start + 1The window length, and the reason the dictionary stores indices rather than counts. Storing counts works too, but then the left edge has to walk, and the code gets longer.
Change one thing
Raise k to 6 and compare the two operation counts again. The gap grows with the window, because the naive version pays for it every step.
Run longest_unique on "abba". The second a is what the seen[ch] >= start guard is protecting against — drop it and the answer is wrong.
Adapt the fixed window to a running average. Same two lines, and it is how a moving average over a data stream is actually computed.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
The fixed-size window updates its sum with one line. Which?
Add what entered, subtract what left. Carrying the value forward instead of rebuilding it is what turns O(n·k) into O(n).
In the longest-unique-substring window, why is the check 'ch in seen and seen[ch] >= start' rather than just 'ch in seen'?
Only a repeat inside the current window matters. Drop the second condition and "abba" gives the wrong answer.
Storing the last index of each character rather than a count lets the left edge:
Both approaches are correct; jumping keeps the scan clearly linear and the code short.
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).
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.