What is it? #
A sliding window keeps a range over a sequence and moves it along, updating the answer as elements enter and leave instead of recomputing from scratch.
Fixed-size windows move both edges together — useful for rolling averages and any "best block of k items" question.
Variable-size windows grow the right edge until a condition breaks, then shrink from the left until it holds again. That shape solves most "longest or shortest range satisfying X" problems.
The gain is the same as two pointers: a nested loop becomes a single pass, because each element enters and leaves the window exactly once.
Think of it like this #
Looking at a long street through a train window. As the train moves, one building leaves the view and another enters. You do not re-count every building in sight — you subtract the one that left and add the one that arrived.
Simple example #
Three problems: the highest total of any three consecutive days of sales, the longest stretch of distinct characters in a string, and the shortest run of numbers adding up to at least a target.
Code #
# 1. Fixed window: best sum of any k consecutive values
def max_window_sum(values, k):
if len(values) < k:
return None
window = sum(values[:k])
best = window
for i in range(k, len(values)):
window += values[i] - values[i - k] # add entering, remove leaving
best = max(best, window)
return best
sales = [120, 90, 300, 40, 260, 180, 75]
print(max_window_sum(sales, 3)) # 600 -> 300 + 40 + 260
# 2. Variable window: longest substring with no repeated character
def longest_unique(text):
last_seen = {}
start = best = 0
for end, char in enumerate(text):
if char in last_seen and last_seen[char] >= start:
start = last_seen[char] + 1 # shrink past the duplicate
last_seen[char] = end
best = max(best, end - start + 1)
return best
print(longest_unique("abcabcbb")) # 3 -> "abc"
print(longest_unique("pwwkew")) # 3 -> "wke"
# 3. Variable window: shortest run summing to at least target
def shortest_subarray(nums, target):
start = total = 0
best = float("inf")
for end, value in enumerate(nums):
total += value
while total >= target: # shrink while still valid
best = min(best, end - start + 1)
total -= nums[start]
start += 1
return 0 if best == float("inf") else best
print(shortest_subarray([2, 3, 1, 2, 4, 3], 7)) # 2 -> [4, 3]
# 4. Fixed window with a counter: any anagram of a pattern
from collections import Counter
def find_anagrams(text, pattern):
if len(pattern) > len(text):
return []
need = Counter(pattern)
window = Counter(text[:len(pattern)])
found = [0] if window == need else []
for i in range(len(pattern), len(text)):
window[text[i]] += 1 # entering
leaving = text[i - len(pattern)]
window[leaving] -= 1
if window[leaving] == 0:
del window[leaving] # keep the counter clean
if window == need:
found.append(i - len(pattern) + 1)
return found
print(find_anagrams("cbaebabacd", "abc")) # [0, 6]Fixed window of 3 over [120, 90, 300, 40, 260, 180, 75]
[120 90 300] 40 260 180 75 sum 510
120 [90 300 40] 260 180 75 sum 430 (-120 +40)
120 90 [300 40 260] 180 75 sum 600 (-90 +260)How it works #
In max_window_sum, the first window is summed once. After that, each move adds the entering value and subtracts the leaving one — two operations regardless of window size. Recomputing the whole sum each time would be O(n·k); this is O(n).
longest_unique grows the window by moving end forwards. When the incoming character was already seen inside the current window, start jumps past its previous position. The check last_seen[char] >= start is essential — a duplicate that occurred before the window started does not matter.
shortest_subarray grows until the condition is satisfied, then shrinks from the left while it stays satisfied, recording the best length each time. Although there is a while inside a for, each element is added once and removed at most once, so the total work is still O(n).
find_anagrams slides a fixed window and maintains a character counter incrementally. Deleting zero-count keys matters: without it, the comparison against need fails because the dictionaries differ by entries mapping to zero.
The general recipe: decide what state the window holds (a sum, a counter, a set), decide when to grow, decide when to shrink, and update the state on both edges instead of recalculating.
Sliding windows work when adding and removing elements can update the answer incrementally. If the answer must be rebuilt from the whole window each time, the technique gives nothing.
Real-world use #
Rate limiting is a sliding window: count requests within the last sixty seconds, dropping older entries as time moves. Both fixed and sliding-window rate limiters are standard, and the System Design track covers them.
Monitoring systems compute rolling averages, moving maximums and percentiles over recent time windows for dashboards and alerts.
Stream processing frameworks are built around windows: sum sales per rolling hour, detect anomalies against a recent baseline, count unique users in the last five minutes.
In text processing, sliding windows find matching patterns, detect plagiarism through shared substrings, and tokenise sequences for machine learning.
Anywhere you see "in the last N" or "the best consecutive run", a window is the right shape.
Common mistakes #
- Recomputing the whole window each step, which throws away the entire benefit.
- Forgetting to remove the leaving element from the window state.
- Mishandling stale entries in a variable window — check that a seen index is still inside the window.
- Leaving zero-count keys in a counter, breaking equality comparisons.
- Applying a window to a problem where the answer cannot be updated incrementally.
Practice #
Write three functions: the maximum average of any k consecutive readings; the length of the longest substring containing at most two distinct characters; and a rate limiter class that reports whether a request is allowed given at most N requests in the last S seconds.