Sliding Window ·

Introduction
#

Sliding windows handle problems about contiguous subarrays / substrings. Enumerating every range is O(n^2); a sliding window moves both boundaries only to the right, so each element enters and leaves once, giving O(n).

The key is that when the window moves, update only the element coming in and the one going out; never recompute the whole window.

Form	How the window moves	Example
Fixed size	One in on the right, one out on the left	Max sum of length `k`, per-window statistics
Variable, longest	Grow right; when invalid, shrink left until valid	Longest subarray with at most `k` zeros
Variable, shortest	Grow right; while valid, shrink left as far as possible	Shortest subarray with sum at least `k`
Counting subarrays	`right - left + 1` valid subarrays end at `right`	“Exactly K” as “at most K” minus “at most K - 1”
Window max / min	Monotonic deque	Sliding window maximum

Variable windows need monotonicity: as the window grows, the condition only gets harder (or easier) to satisfy. With negative numbers or a non-monotonic condition, prefix sums plus a hash map are usually the tool instead.

Template 1: Fixed-size window
#

window = 0
for right, x in enumerate(nums):
    window += x                          # in
    if right >= k:
        window -= nums[right - k]        # out
    if right >= k - 1:                   # update only once the window is full
        res = max(res, window)

What the window maintains is not always a sum:

Hash map / count array: how many distinct values are in the window (LC 2841, 2461), or the x-th smallest negative (LC 2653, small value range, so a count array).
Turn “remove a part” into “keep a part”: taking k cards from the ends = keeping a contiguous middle of length n - k with minimum sum (LC 1423); removing a length-k substring = the remaining displacement = total displacement minus the window’s (LC 3694).
Circular arrays: concatenate the array with itself, or use i % n (LC 2134, 1888).
Rolling hash: multiply / divide by power as the window moves, touching only the ends (LC 2156).

Template 2: Variable window, longest
#

left = 0
for right, x in enumerate(nums):
    add(x)
    while window_invalid():
        remove(nums[left])
        left += 1
    res = max(res, right - left + 1)     # always valid after shrinking

At most one 0: the longest all-1s run after deleting one element is the longest window with at most one 0, minus 1 (LC 1493).

Template 3: Variable window, shortest
#

left = 0
for right, x in enumerate(nums):
    add(x)
    while window_valid():
        res = min(res, right - left + 1) # update while valid, then try shrinking
        remove(nums[left])
        left += 1

Sum of distinct values at least k (LC 3795): a value appearing several times counts once. Record each value’s last position, and when the left boundary leaves, subtract it only if that was its last occurrence.

Template 4: Counting subarrays
#

Every subarray ending at right with its left end in [left, right] is valid, which is right - left + 1 of them:

def at_most(k):
    left = count = 0
    for right, x in enumerate(nums):
        add(x)
        while exceeds(k):
            remove(nums[left])
            left += 1
        count += right - left + 1
    return count

return at_most(k) - at_most(k - 1)       # exactly k

“Exactly K” is not monotonic, but “at most K” is, so subtract two at-most counts (LC 1248). When the condition, such as “cost <= k”, is monotonic itself, count directly (LC 3835).

The “at least K” form: while the window is valid, keep shrinking the left until it just becomes invalid. Then any left end in [0, left) is valid, so count += left:

left = count = 0
for right, x in enumerate(nums):
    add(x)
    while window_valid():
        remove(nums[left])
        left += 1
    count += left                        # left ends in [0, left) are all valid

(LC 2962, 1358, 3325, 3298, 2537). “Exactly K” can also be “at least K” minus “at least K + 1” (LC 3306).

Template 5: Monotonic deque for window extremes
#

from collections import deque

max_q = deque()                          # indices, values decreasing
for right, x in enumerate(nums):
    while max_q and nums[max_q[-1]] <= x:
        max_q.pop()                      # dominated by x, can never be the max
    max_q.append(right)
    left = right - k + 1                 # fixed size k; for variable windows the condition sets left
    if max_q[0] < left:
        max_q.popleft()                  # expired: outside the window
    if left >= 0:
        res.append(nums[max_q[0]])       # window maximum

Keep the two conditions separate: the back drops dominated indices, the front drops expired ones. For both max and min, use two deques (LC 3835).

DP + monotonic deque: dp[i] = nums[i] + max(0, max of dp[i-k..i-1]), and the max of the previous k values of dp is a sliding window maximum (LC 1425).

Key Parameters
#

left, right: the window is [left, right], length right - left + 1.
For fixed size, the outgoing element is nums[right - k] and the window is full when right >= k - 1.
Counting hash maps: delete keys that drop to 0 so len() means “number of distinct values”.

Complexity
#

Each element enters and leaves the window once: time O(n). With a hash map, space is O(distinct values in the window).

Common Mistakes
#

These are all mistakes I actually made while practicing:

Wrong variable for the outgoing element: after copy-pasting, the left element was checked against the right element’s expected value (LC 1888).
Discarded elements left in the counts: an arrival the rule discards should not be subtracted again when it leaves the window (LC 3679).
Missing the first window: updating the answer only when i - k >= 0 skips the window ending at i == k - 1 (LC 3694).
Using the total sum when the problem wants the sum of distinct values (LC 3795).
Not checking that the window length equals the target (LC 2953).
Powers without a modulo: recomputing power ** k as a big integer each step, TLE (LC 2156).
Mixing “expired” and “dominated” into one deque condition (LC 3835).
Not updating counts while shrinking: the while loop moved left but never subtracted the leaving element (LC 2537).
A hard-coded leave threshold: an “at least k times” counter should drop when a count goes from k to k - 1, but I wrote == 1 (LC 3325).