Sliding window

The sliding window turns questions about every contiguous subarray into a single linear pass by maintaining an incrementally updatable summary of the current range. Its correctness rests on two preconditions that candidates routinely skip: the range must be contiguous, and the constraint must move monotonically as the range grows. This guide develops the fixed and variable forms, the frequency-map and monotonic-deque state that support the harder constraints, the at-most decomposition for exact counts, and the amortised argument that justifies calling a loop with a nested shrink linear. It ends with the production forms of the same structure — moving averages, rate limiters, and time-based eviction — where the choice between a count window and a time window is a guarantee, not a detail.

the sliding-window idea

A sliding window answers questions about every contiguous subarray without enumerating them, by maintaining a summary of the current window and updating it incrementally.

Extending the window on the right adds one element's contribution and shrinking it on the left removes one, so each boundary move is O(1) and the whole scan is linear.

Add and remove are O(1); recomputing the sum inside the loop is not.

# Linear: each boundary move touches one element.
total += a[right]; total -= a[left]

# Quadratic in disguise - the loop looks identical from outside:
total = sum(a[left:right + 1])

At n = 100,000 with a window of 1,000 that is 100,000 operations against 100 million.

Interview trap. Recomputing the window's summary from scratch after each move restores the quadratic cost the pattern exists to avoid, even though the code still looks like a sliding window.

Engineering practice. Make add and remove explicit operations on the summary, and check that neither of them loops over the window.

fixed-size windows

When the window length is given, the two boundaries move in lockstep and the loop reduces to one add and one remove per step.

The first k elements are accumulated to prime the summary, and thereafter each iteration adds the entering element and removes the leaving one before recording the answer.

Prime the window, then record; recording early reports short prefixes.

k, best = 3, float("-inf")
total = sum(a[:k])                      # prime
best = total
for right in range(k, len(a)):
    total += a[right] - a[right - k]    # one add, one remove
    best = max(best, total)

On a of length 2 with k = 3 the primer already covers the whole input; guard it explicitly.

Interview trap. Recording the answer before the window has reached full size reports results for short prefixes that the problem never asked about.

Engineering practice. Prime the window explicitly, then record only once the window is full, and test the case where the input is shorter than the window.

variable-size windows

When the window is defined by a condition rather than a length, the right boundary always advances and the left boundary advances only while the condition is violated.

The inner shrink loop is not nested work in the complexity sense, because the left boundary advances at most n times over the whole run.

The inner while is not nested work: left advances at most n times over the whole run.

left = total = 0
for right, v in enumerate(a):
    total += v
    while total > limit:      # amortised: left moves n times in total, not n times per right
        total -= a[left]; left += 1
    best = max(best, right - left + 1)

Interview trap. Counting the inner loop as nested iteration leads to a wrong quadratic claim, and the opposite error — shrinking with an if rather than a while — leaves the window invalid.

Engineering practice. Use a while for the shrink, justify the linear bound by the monotonic left boundary, and assert the window's validity at the point the answer is recorded.

the window validity invariant

Every sliding-window solution rests on an invariant that the window satisfies the constraint at the moment the answer is read.

The shrink loop is what restores the invariant after an extension breaks it, so the answer must be recorded after shrinking, not before.

Record after shrinking, or you measure a window that breaks the constraint.

for right, v in enumerate(a):
    add(v)
    while invalid():
        remove(a[left]); left += 1
    best = max(best, right - left + 1)   # here, not inside the while

Interview trap. Recording the answer inside or before the shrink loop reports a window that is not valid, which produces answers that are too large.

Engineering practice. Order the loop body as extend, restore, record, and write the invariant as a comment where the answer is taken.

monotonicity is a precondition

The technique requires that extending a window can only move the constraint in one direction — otherwise shrinking from the left is not justified.

With all-positive values, a longer window has a larger sum, so a too-large sum can only be fixed by shrinking; with mixed signs that implication fails and the window may need to grow to become valid again.

With a negative value the constraint stops moving in one direction.

a, k = [1, -1, 5], 5
# Window [1, -1] sums to 0 < 5, so a shrink-on-too-large rule never fires,
# yet extending to [1, -1, 5] = 5 is only reachable by growing.
# Use prefix sums with a hash map instead when values can be negative.

Interview trap. Applying the pattern to an array containing negative numbers is the classic failure, and it produces plausible but wrong answers rather than an obvious crash.

Engineering practice. Check the monotonicity condition explicitly; when it does not hold, switch to prefix sums with a hash map or to a different structure entirely.

counting characters inside the window

A frequency map of the window's contents supports constraints about distinctness, coverage, and repetition in constant time per boundary move.

Entering an element increments its count and leaving decrements it; the number of distinct elements is maintained by watching for counts that reach or leave zero.

Delete keys at zero, or len(counts) overcounts distinct elements.

from collections import defaultdict
counts = defaultdict(int)
counts[a[left]] -= 1
if counts[a[left]] == 0:
    del counts[a[left]]          # without this, len(counts) counts departed elements

Interview trap. Leaving zero-valued entries in the map while using the map's size as the distinct count silently overcounts.

Engineering practice. Either delete keys when their count reaches zero or keep a separate distinct counter, and pick one convention for the whole codebase.

longest substring without repeats

The longest window with all-distinct elements is found by shrinking whenever the entering element is already inside the window.

Storing each element's last seen position lets the left boundary jump directly past the previous occurrence rather than stepping one at a time.

Take the maximum, or a stale position drags left backwards.

last, left, best = {}, 0, 0
for right, ch in enumerate(s):
    if ch in last:
        left = max(left, last[ch] + 1)    # max, not assignment
    last[ch] = right
    best = max(best, right - left + 1)

# "abba": without max, left jumps back to 1 at the final 'a' and the answer becomes 3.

Interview trap. Jumping the left boundary to the stored position without taking a maximum against its current value moves it backwards when the stored position is stale.

Engineering practice. Advance the left boundary monotonically by taking the maximum with its current value, which is what keeps the linear bound and the correctness together.

minimum window covering a requirement

The smallest window containing all required elements is found by extending until the requirement is met, then shrinking while it stays met.

A single counter tracking how many requirements are currently satisfied avoids rescanning the requirement map on every move.

One satisfied counter avoids rescanning the requirement map each step.

need = Counter(t); have, missing = defaultdict(int), len(need)
for right, ch in enumerate(s):
    have[ch] += 1
    if ch in need and have[ch] == need[ch]:
        missing -= 1                       # crossed the threshold exactly once
    while missing == 0:
        ...                                # shrink and record

Comparing the two maps every step would add a factor of the alphabet size.

Interview trap. Comparing the whole requirement map against the window map on each step is correct but reintroduces a factor proportional to the alphabet size.

Engineering practice. Maintain the satisfied-requirement counter incrementally, and update it only when a count crosses the required threshold.

at-most as a building block

A count of subarrays with exactly k distinct elements is the count with at most k minus the count with at most k minus one.

The at-most version is a straightforward sliding window because the constraint is monotone, while the exact version is not; the subtraction recovers it.

Exactly k is the difference of two monotone counts.

def at_most(a, k): ...           # standard shrink-when-distinct-exceeds-k window
exactly_k = at_most(a, k) - at_most(a, k - 1)

# a = [1, 2, 1, 2, 3], k = 2 -> at_most(2)=12, at_most(1)=5, exactly=7

Interview trap. Trying to maintain an exactly-k window directly produces a shrink condition that has no consistent direction and a solution that fails on the boundaries.

Engineering practice. Decompose exact constraints into a difference of monotone ones, and validate the decomposition on small inputs by brute force.

counting windows rather than measuring them

When the answer is a count of qualifying subarrays, each valid right boundary contributes a number of windows equal to the span of valid left boundaries.

Because the left boundary is monotone, the number of valid windows ending at the current position is the distance between the two pointers, added in constant time.

Each valid right boundary contributes right - left + 1 windows, not one.

count += right - left + 1        # every left in [left, right] gives a valid window

# a = [1, 1, 1], limit >= 3: contributions 1 + 2 + 3 = 6 subarrays, not 3.

Interview trap. Incrementing the answer by one per valid window position undercounts by a factor that grows with the window length.

Engineering practice. Derive the contribution formula from the invariant, and check it against a brute-force count on inputs of length up to a dozen.

the monotonic deque for window maxima

The maximum of every window of fixed size is computed in linear total time with a deque holding indices in decreasing value order.

Before inserting, every element smaller than the entering one is popped from the back, because it can never be the maximum while the newer, larger element is in the window; the front is popped when it leaves the window.

Store indices so eviction by position is possible at all.

from collections import deque
dq, out = deque(), []
for i, v in enumerate(a):
    while dq and a[dq[-1]] <= v: dq.pop()        # evict by value from the back
    dq.append(i)
    if dq[0] <= i - k: dq.popleft()              # evict by position from the front
    if i >= k - 1: out.append(a[dq[0]])

# a = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 -> [3, 3, 5, 5, 6, 7]

Each index is pushed once and popped once: O(n) total, not O(nk).

Interview trap. Storing values rather than indices makes it impossible to tell when the front has left the window, and the maximum then goes stale.

Engineering practice. Store indices, evict from the front by position and from the back by value, and each element enters and leaves once — which is the linear-time argument.

why a heap is the wrong structure here

A heap gives the window maximum in logarithmic time but cannot remove an arbitrary element that has left the window.

The usual repair is lazy deletion — keep popping the top while it is out of range — which is correct but adds a logarithmic factor and unbounded memory in the worst case.

Lazy deletion keeps every element alive in the worst case.

import heapq
h = []
for i, v in enumerate(a):
    heapq.heappush(h, (-v, i))
    while h[0][1] <= i - k: heapq.heappop(h)     # discard out-of-range tops

On a strictly decreasing input nothing is ever evicted early: the heap holds all n elements, where the deque holds k.

Interview trap. Assuming the heap solution is equivalent misses that its worst case holds every element simultaneously while the deque holds only the useful ones.

Engineering practice. Use the deque for fixed windows, and reserve the lazy-deletion heap for cases where the eviction rule is not positional.

windows over streams

The pattern extends to unbounded streams, where the window is the only state retained and old elements can never be revisited.

Memory is bounded by the window rather than by the input, which is what makes the technique usable where the full dataset does not fit.

The window is the only state, so memory is O(k) regardless of stream length.

from collections import deque
window = deque(maxlen=1000)       # bounded by construction
for event in stream:              # unbounded input
    window.append(event)          # oldest is dropped automatically

Any solution that indexes backwards into the full input cannot be applied here, however linear it looks.

Interview trap. Any solution that indexes backwards into the input arbitrarily cannot be applied to a stream, however linear it looks on an array.

Engineering practice. State whether the algorithm needs random access, and if it does, say so before proposing it for streaming data.

time-based windows

A window defined by a time span rather than an element count evicts by timestamp, so its element count varies and can reach the whole input.

Eviction compares the front element's timestamp against the current time minus the span, which means bursts produce large windows and idle periods produce empty ones.

A 60-second window holds 5 events when idle and 50,000 in a burst.

from collections import deque
window = deque()
def record(now, event, span=60.0, cap=100_000):
    window.append((now, event))
    while window and window[0][0] <= now - span: window.popleft()
    if len(window) > cap: raise Overloaded    # bound both dimensions

Interview trap. Sizing a buffer for a time window as though the element count were fixed produces an outage exactly when traffic spikes.

Engineering practice. Bound the structure by both time and count, and decide explicitly what to do when the count bound is hit first.

the deque as the underlying container

Sliding windows need cheap insertion and removal at both ends, which is what a double-ended queue provides and a plain array does not.

Removing from the front of a contiguous array is O(n) because everything shifts, while a deque's block or ring layout makes both ends O(1).

list.pop(0) is O(n); deque.popleft() is O(1).

import timeit
timeit.timeit("a.pop(0)", "from collections import deque; a=list(range(100_000))", number=50_000)   # ~0.9s
timeit.timeit("a.popleft()", "from collections import deque; a=deque(range(100_000))", number=50_000)  # ~0.004s

Interview trap. Using a list and removing from index zero turns a linear algorithm into a quadratic one while leaving the code looking correct.

Engineering practice. Choose the deque type deliberately, and check the documented complexity of front removal rather than assuming it.

windows on two dimensions

A two-dimensional window is usually decomposed into a one-dimensional window applied twice rather than maintained directly.

Sliding horizontally over each row produces row-wise results, and sliding vertically over those results produces the rectangle answer, keeping the total linear in the cell count.

Slide horizontally, then vertically, over the intermediate result.

rows = [[window_max(row, k) for row in grid]]        # pass 1: per row
cols = transpose_window_max(rows, k)                 # pass 2: down the columns

Total work is O(rows x cols) for a k x k maximum, independent of k.

Interview trap. Maintaining a genuine two-dimensional summary incrementally is possible but error-prone, and the decomposition is both simpler and easier to test.

Engineering practice. Decompose by dimension, verify each pass independently, and keep the intermediate array so the two stages can be tested separately.

prefix sums as the alternative

When the constraint is not monotone, prefix sums with a hash map replace the sliding window and remain linear.

Instead of maintaining a window, the scan records every prefix value and asks how many earlier prefixes would make the current range satisfy the constraint.

When values can be negative, the window rule is unsound and prefixes are not.

from collections import defaultdict
seen, running, count = defaultdict(int), 0, 0
seen[0] = 1
for v in a:                       # a may contain negatives
    running += v
    count += seen[running - k]
    seen[running] += 1

Interview trap. Reaching for a window on an array with negative values is the standard mistake; the prefix-map formulation is the correct substitution.

Engineering practice. Recognise the non-monotone case from the value domain, and switch formulations rather than patching the window's shrink condition.

recording the window rather than its size

Returning the window itself requires storing its boundaries at the moment the best answer was seen, not at the end of the loop.

The pointers keep moving after the optimum, so the boundaries must be captured alongside the best value.

Capture the boundaries with the best value; the pointers keep moving afterwards.

if right - left + 1 > best_len:
    best_len, best_start = right - left + 1, left    # captured at the optimum
return s[best_start:best_start + best_len]           # not s[left:right + 1]

Interview trap. Slicing the array at the end using the final pointer positions returns whatever window the loop happened to finish with.

Engineering practice. Capture the start and length together with the best value, and return the slice from the captured values.

empty and degenerate windows

The empty window and the whole-array window are the two cases where sliding-window code most often fails.

An empty input never enters the loop and must return the identity value for the aggregate, while an input that is entirely valid never triggers the shrink loop.

Initialising the best to 0 returns 0 for an all-negative array.

best = float("-inf")     # not 0
total = 0
for v in a:
    total = max(v, total + v)
    best = max(best, total)

# a = [-3, -1, -2] -> -1, which is correct; a zero initialiser would return 0.

Interview trap. Initialising the best answer to zero rather than to a proper identity gives wrong results when every valid answer is negative.

Engineering practice. Initialise with an explicit sentinel or with the first element, and cover empty, single-element, and all-valid inputs in tests.

the amortised argument

The linear bound comes from each element entering the window once and leaving once, not from the loop structure.

Both boundaries are monotone, so the total number of boundary moves is bounded by twice the input length regardless of how the moves are distributed.

2n boundary moves in total, whatever the distribution.

# right advances exactly n times.
# left advances at most n times across the entire run, because it never decreases.
# Therefore the loop body runs at most 2n times: O(n).

Interview trap. A shrink loop that can restart the left boundary from an earlier position breaks the amortisation and the bound no longer holds.

Engineering practice. Verify no assignment moves a boundary backwards, and when one must, account for the real cost rather than quoting the pattern's bound.

window state that is not a simple aggregate

The pattern requires the window summary to be updatable on both add and remove, which rules out aggregates that are not invertible.

Sums and counts are removable; maxima are not, which is exactly why the maximum case needs the monotonic deque rather than a running variable.

Sums are removable; maxima are not, which is why the deque exists.

total -= a[left]                 # exact inverse
if running_max == a[left]:       # no inverse: the previous maximum is unknown
    running_max = max(a[left + 1:right + 1])   # O(k) - the bound is gone

Interview trap. Keeping a running maximum and expecting it to be correct after the maximum element leaves the window is the most common instance of this error.

Engineering practice. Ask whether the aggregate has an inverse; if it does not, choose a structure that can recompute it in amortised constant time.

windows with a shrink budget

Problems that permit k modifications inside the window become sliding-window problems where the constraint is the modification count.

The window tracks how many changes it would take to satisfy the property, and shrinks whenever that count exceeds the budget.

Track the cost of achieving the property, not the property itself.

# Longest run of 1s allowing k flips: the window's cost is its count of zeros.
zeros = left = best = 0
for right, v in enumerate(a):
    zeros += v == 0
    while zeros > k:                 # cost is monotone in window length
        zeros -= a[left] == 0; left += 1
    best = max(best, right - left + 1)

Interview trap. Tracking the property directly rather than the cost of achieving it makes the constraint non-monotone and the shrink rule unsound.

Engineering practice. Reformulate the constraint as a cost that grows with the window, then apply the standard extend-and-shrink loop.

duplicate detection within a distance

Asking whether two equal elements occur within k positions is a fixed-size window over a set.

The set holds the last k elements; each step tests membership, inserts the entering element, and removes the one that has fallen out of range.

Evict by position, not by the value just inserted.

window = set()
for i, v in enumerate(a):
    if i > k: window.discard(a[i - k - 1])    # the element that fell out of range
    if v in window: return True
    window.add(v)
return False

# a = [1, 2, 1], k = 2 -> True; k = 1 -> False

Interview trap. Removing the wrong element on eviction — the entering one rather than the departing one — leaves the set growing and the answer wrong.

Engineering practice. Index the eviction by position rather than by value, and test with an input where the same value appears at both window ends.

windows in production systems

Rate limiters, moving averages, and anomaly detectors are sliding windows, and the same monotonicity and eviction questions apply.

A fixed-count window gives a stable memory bound; a fixed-time window gives a stable semantic meaning; the two disagree under bursty traffic and one of them has to be chosen.

A count window and a time window disagree exactly under a burst.

Window	Memory	Meaning under a 10x burst
Last 1,000 requests	fixed	covers 6 seconds instead of 60
Last 60 seconds	unbounded	holds 10x the entries

A rate limiter promises requests per unit time, so the time window is the one that matches the guarantee; the count bound exists to keep memory finite.

Interview trap. Approximating a time window with a count window is correct only if arrival rate is stable, which is exactly what a rate limiter cannot assume.

Engineering practice. Choose the window semantics from the guarantee being made, and bound the other dimension so the structure cannot grow without limit.

recognising the pattern

The sliding window applies when the answer concerns contiguous ranges and the constraint changes monotonically as the range grows.

Contiguity is what makes incremental update possible, and monotonicity is what makes one-directional shrinking correct; losing either sends the problem to a different technique.

Contiguity and monotonicity, or it is a different technique.

Question	Window?
Longest subarray with sum <= k, all values positive	yes
Longest subarray with sum <= k, values may be negative	no - prefix sums
Longest increasing subsequence	no - elements need not be adjacent
Maximum of every k-length window	yes, with a monotonic deque

Interview trap. Reaching for a window on subsequence problems, where elements need not be adjacent, produces answers that are wrong in a way small examples hide.

Engineering practice. Confirm both contiguity and monotonicity before writing the loop, and name the alternative technique when either fails.