Sliding Window

TL;DR

When the brute force is “for every subarray, recompute something from scratch,” sliding window is almost always the fix. You hold a [left, right] range over the sequence and maintain a running aggregate — sum, count, hash map of frequencies, max via deque — that updates in O(1) when an element enters on the right or leaves on the left. Total work is O(n) because each index enters the window once and leaves at most once.

The pattern comes in two flavors. Fixed window: width is always exactly k. As right advances, left = right - k + 1 follows mechanically. Used for rolling means, “max sum of any k consecutive elements,” and any moving aggregate over a metrics stream. Dynamic window: width changes. The window grows by default and shrinks from the left only when some invariant breaks. Used for “longest substring with at most 2 distinct chars,” “smallest subarray with sum ≥ S,” and almost every string-matching variant.

If the question is over a contiguous subarray or substring and asks for a min/max length, a count, or a per-window aggregate, this is your pattern. If the elements can be non-contiguous, or the answer requires reordering, it isn’t — reach for DP, hashing, or a sort instead.

The picture in your head

A magnifying glass slides across a long sentence, framing exactly K characters at a time. Each step right: one character enters the lens on the right, one drops off on the left. The glass never re-reads what it already saw — whatever you computed for the previous frame is patched in O(1) to get the new frame’s value. That patch (add the entering element, subtract the leaving one) is the entire trick.

For the dynamic flavor, picture the same magnifying glass but with a stretchy frame. The right edge always advances by one. The left edge stays put as long as the window is “valid” by some rule, and only when the new character on the right breaks the rule does the left edge ratchet forward until validity is restored. The frame breathes; it never goes backwards.

The problem it solves

Take the canonical setup: given an array nums of length n and a window size k, return the maximum sum of any contiguous subarray of length k. The textbook brute force is two nested loops:

def max_sum_brute(nums, k):
    best = float("-inf")
    for i in range(len(nums) - k + 1):
        s = 0
        for j in range(i, i + k):     # recompute the whole window
            s += nums[j]
        best = max(best, s)
    return best

That’s O(n × k) time and O(1) space. The cost balloons fast: at n = 10⁴ and k = 100, you’re doing 10⁶ ops — fine. At n = 10⁶ and k = 10⁴, it’s 10¹⁰ ops — dead in production, your function never returns within a useful timeout. And every one of those inner-loop additions is wasted work: the window at position i+1 shares k - 1 elements with the window at i.

Sliding window asks one question of the brute force: “instead of recomputing the aggregate from scratch, can I patch the previous one?” For sums, yes — subtract the element that just left, add the one that just entered. The inner loop disappears; total time drops to O(n). You’ve kept O(1) extra space and changed the cost from O(n × k) to O(n), regardless of how big k gets.

When to reach for it

Signals it’s the right move:

• The answer is over contiguous subarrays or substrings.
• Brute force is “loop i, loop j ≥ i, compute aggregate over nums[i..j]” — O(n²) or O(n × k) — and the aggregate updates incrementally as you grow or shrink by one element.
• The problem fixes a window size k (“every subarray of size k…”).
• The problem asks for the shortest or longest contiguous range that satisfies a monotone condition (sum ≥ target, ≤ k distinct chars, all characters of t covered).

Signals it’s not sliding window: the elements need to be reordered (sort it), the subset doesn’t have to be contiguous (DP or hashing), or the “condition holds” property isn’t monotone in window size — meaning extending the window can suddenly fix a broken state, which kills the shrink rule.

Flavor 1 — fixed window

Given an array and a window size k, find the maximum sum of any contiguous subarray of length k.

def max_sum_window(nums: list[int], k: int) -> int:
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # add new, drop old
        best = max(best, window)
    return best

Worked example. nums = [2, 1, 5, 1, 3, 2], k = 3. Initial window is nums[0..2] = [2, 1, 5] with sum 8.

Answer: 9 — the window [5, 1, 3] ending at index 4. The update += nums[right] - nums[right - k] keeps current_sum equal to the sum of exactly the last k elements ending at right. Patch, don’t recompute.

Flavor 2 — dynamic window (shrink while invariant broken)

Given a string, find the length of the longest substring without repeating characters. The window grows by default; when a duplicate appears, shrink from the left until the invariant (“no repeats”) is restored.

def longest_unique(s: str) -> int:
    last_seen: dict[str, int] = {}   # char -> most recent index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the duplicate
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Worked example. s = "abcabcbb".

Answer: 3. The invariant: at the top of every iteration, s[left..right] contains no repeated character. When right introduces a duplicate that falls inside the window (last_seen[ch] >= left), left jumps to one past the previous occurrence to restore the invariant in a single step.

The “shrink while invariant is broken” skeleton generalises:

• At most k distinct chars — keep a count map; shrink while len(seen) > k.
• Smallest subarray with sum ≥ S — shrink while window_sum >= S, recording length each time before the shrink.
• Minimum window substring covering t — shrink while every char of t is still covered, recording the minimum.

The condition inside the shrink loop is the problem.

Why it works — the invariant

Sliding window correctness rests on two facts. First, the aggregate (window_sum, last_seen, deque of maxes) is incrementally maintained: adding or removing one element costs O(1), so per-step work is constant. Second, left and right are monotone non-decreasing — each index is added to the window once (when right reaches it) and removed at most once (when left passes it), for a total of 2n pointer moves across the whole run.

The dynamic flavor adds a third fact: the condition is monotone in window size. If s[left..right] violates the condition, no longer window starting at the same left can satisfy it either, so advancing left is the only useful move. If that monotonicity doesn’t hold — extending the window could fix a broken state — sliding window breaks down and you need a different tool (prefix sums plus a hash map, segment tree, etc.).

Complexity & memory tradeoffs

Sliding window’s edge isn’t just speed — it’s that you keep brute force’s O(1) (or near-O(1)) memory while collapsing the time band. Prefix sums match the time but pay O(n) memory and only work for additive aggregates. A sort-based approach destroys contiguity and answers a different question. The only situation where sliding window loses is when the underlying condition isn’t monotone in window size, in which case the shrink rule is unsound and you have to reach for something heavier.

Common pitfalls

• Off-by-one expanding right. The window [right - k + 1 .. right] is k wide. The patch update is += nums[right] - nums[right - k] — the index leaving is right - k, not right - k + 1. This is the classic fixed-window bug.
• Forgetting to update state when shrinking. Every left++ must decrement the count in the map (or subtract from window_sum). Half the bugs in this pattern are “I moved the pointer but not the bookkeeping.”
• Returning length vs index. right - left + 1 is the length of s[left..right] inclusive. right - left is wrong by one. For “return the substring” problems, slice s[left:right+1], not s[left:right].
• Sign error when an element leaves. For sums, leaving means subtract; for “count of elements equal to X,” leaving means decrement. Writing window += nums[right - k] instead of -= silently produces nonsense that looks plausible on small inputs.
• if instead of while in the shrink. A single if only drops one element. If right introduces a state that needs multiple left++ to restore (e.g. a char that pushes the count above 2 when the window already had two pairs), if leaves the invariant broken.
• Stale hash-map keys. seen[ch] == 0 is not the same as ch not in seen. For “k distinct” problems, delete the key when the count hits zero or check > 0 explicitly — otherwise len(seen) overcounts.

Where you see this in production

• pandas.Series.rolling(k).mean() is a fixed window sum divided by k, implemented exactly like Flavor 1 over a NumPy buffer. The same primitive backs rolling().std(), rolling().sum(), and the Bollinger bands in every quant notebook.
• Prometheus rate(metric[5m]) computes a delta over a fixed 5-minute window sliding across a time series at query time — fixed-window aggregate evaluated at every scrape boundary, identical skeleton to Flavor 1 with timestamps as the index.
• TCP congestion / receive window in the Linux kernel (tcp_input.c) advances left as ACKs arrive and right as new bytes are received in-order, with the window size dictating how much unacknowledged data the sender may have in flight. Dynamic-window pattern over a byte stream.
• NGINX / Envoy rate limiters (ngx_http_limit_req_module, Envoy’s local_ratelimit) keep a sliding log of recent request timestamps, drop any older than now - window, and reject when the count exceeds budget — Flavor 2 with now as right and timestamp eviction as the shrink.
• Tokenizer chunking for long-context LLMs (Hugging Face’s return_overflowing_tokens with stride) walks a fixed window of max_length tokens with a stride-sized shift, producing overlapping chunks for retrieval and long-document inference. Fixed window, custom step size.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.