The sliding window technique, from first idea to production

Every chart with a “7-day average” line is running a sliding window. So is a rate limiter counting your last minute of requests, a retrieval pipeline cutting a long document into overlapping chunks, and the TCP connection that carried this page to you. Underneath all of them is one idea: when a window moves one step, one thing comes in and one thing goes out, so update the answer instead of working it out again.

That idea turns a whole family of problems from “check every range” into a single pass. It’s also one of the most reliable patterns in coding interviews, because it rewards exactly the habit interviewers look for: noticing that most of the work you’re about to do has already been done.

By the end of this article you’ll be able to spot a sliding window problem, write the fixed and variable versions from one template, explain why a loop inside a loop can still be linear, handle the cases where the simple version breaks (maximums, medians, negative numbers, “exactly K”), and reason about windows over time in stream processors, rate limiters and networks. The last section walks through the windows I run in ezychat.io, including one whose comment and code disagree about what kind of window it is. Start at Beginner if “subarray” is a new word. If you’ve solved “longest substring without repeating characters” before, skip ahead to Advanced.

Beginner: one in, one out

The best three days in a row

Here are a small shop’s sales for ten days:

sales = [4, 2, 12, 3, 1, 9, 8, 2, 6, 5]

The owner asks a simple question: which three days in a row sold the most? Not the three best days scattered across the fortnight, but three consecutive days, because she wants to know when to run a three-day promotion.

A run of consecutive items is called a subarray (or a substring when the items are characters). The run we’re looking at is the window, and its length, three here, is the window size, usually called k.

Recounting every window

The obvious program lines up every possible window and adds it up:

sales = [4, 2, 12, 3, 1, 9, 8, 2, 6, 5]

def best_k_brute(nums, k):
    best = None
    for start in range(len(nums) - k + 1):
        total = 0
        for i in range(start, start + k):    # add up all k numbers, every time
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

print(best_k_brute(sales, 3))
# 19

It’s correct: positions 5 to 7, counting from 0, are the best stretch (9 + 8 + 2). But watch what it does: for the first window it adds 4 + 2 + 12. For the second it adds 2 + 12 + 3. The 2 and the 12 were already added a moment ago, and the program throws that work away and does it again. With ten numbers nobody cares. With a year of hourly data and a window of a week (168 hours), every window repeats 167 additions it has already done.

Sliding: add the newcomer, drop the oldest

Put a strip of card with a three-number hole over the list. Slide it one place right. Exactly one number disappears under the card on the left and exactly one appears on the right. Everything in between stays.

So the new sum is the old sum, plus the number that entered, minus the number that left:

sales = [4, 2, 12, 3, 1, 9, 8, 2, 6, 5]

def best_k(nums, k):
    if not 1 <= k <= len(nums):
        raise ValueError("k must be between 1 and len(nums)")
    total = sum(nums[:k])               # the first window, added up once
    best = total
    for right in range(k, len(nums)):
        total += nums[right]            # the new number enters on the right
        total -= nums[right - k]        # the oldest number leaves on the left
        best = max(best, total)
    return best

print(best_k(sales, 3))
print(best_k(sales, 1), best_k(sales, 10))
# 19
# 12 52

That’s the whole technique in its simplest form. The first window is built the slow way, once. Every later window costs one addition and one subtraction, however big k is. The check at the top matters more than it looks: with k = 0 or k bigger than the list, “the best window” has no meaning, and it’s better to say so than to return a number.

The window is two indices

You never need to copy the window out of the list. Two positions describe it completely: left, the index of its first element, and right, the index of its last. The elements inside are nums[left:right + 1], and the size is right - left + 1. Sliding means moving both one step:

sales = [4, 2, 12, 3, 1, 9, 8, 2, 6, 5]
k = 3

left, right = 0, k - 1
total = sum(sales[left:right + 1])
print(f"left={left} right={right} window={sales[left:right + 1]} sum={total}")
while right + 1 < len(sales):
    right += 1
    total += sales[right]               # enters
    total -= sales[left]                # leaves
    left += 1
    print(f"left={left} right={right} window={sales[left:right + 1]} sum={total}")
# left=0 right=2 window=[4, 2, 12] sum=18
# left=1 right=3 window=[2, 12, 3] sum=17
# left=2 right=4 window=[12, 3, 1] sum=16
# left=3 right=5 window=[3, 1, 9] sum=13
# left=4 right=6 window=[1, 9, 8] sum=18
# left=5 right=7 window=[9, 8, 2] sum=19
# left=6 right=8 window=[8, 2, 6] sum=16
# left=7 right=9 window=[2, 6, 5] sum=13

Thinking in two indices is what makes the next section possible. Here they move together, so the window keeps its size. Once they’re allowed to move separately, the window can grow and shrink.

Step through it yourself. The demo opens on the first full window; press Step to slide, or type your own numbers and window size:

The second mode in the demo, longest without repeats, is the Intermediate section’s first problem. Come back to it then.

Why this is O(n)

“O(n)” (read “order n”) is shorthand for “the work grows in a straight line with the input”: twice the data, twice the work. Here’s the count for both versions, with n numbers and a window of k:

• Recounting looks at about n windows and adds k numbers for each: about n × k additions. Double k and it doubles too.
• Sliding adds k numbers once, then does one addition and one subtraction per remaining position: about 2n operations, and k has dropped out of the cost entirely.

Measured on my laptop (an M1 Pro, Python 3.13), on 100,000 random numbers:

import random, time

def best_k_brute(nums, k):
    best = None
    for start in range(len(nums) - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

def best_k(nums, k):
    total = sum(nums[:k])
    best = total
    for right in range(k, len(nums)):
        total += nums[right] - nums[right - k]
        best = max(best, total)
    return best

random.seed(7)
nums = [random.randint(0, 100) for _ in range(100_000)]
for k in (10, 100, 1_000):
    start = time.perf_counter(); a = best_k_brute(nums, k); brute = time.perf_counter() - start
    start = time.perf_counter(); b = best_k(nums, k); slide = time.perf_counter() - start
    print(f"k={k:>5}: same answer {a == b}, brute {brute:6.2f} s, sliding {slide * 1000:5.1f} ms")
# k=   10: same answer True, brute   0.04 s, sliding   7.6 ms
# k=  100: same answer True, brute   0.30 s, sliding   7.3 ms
# k= 1000: same answer True, brute   2.91 s, sliding   7.4 ms

The brute force gets ten times slower each time k grows ten times. The sliding version doesn’t notice k at all: 7 milliseconds whether the window holds ten numbers or a thousand. That flat line is the reason the technique exists.

When does a problem want a sliding window?

The signals are in the wording. Look for all three:

1. The input is a sequence: an array, a string, a list of events in time order.
2. The question is about a contiguous run: “consecutive”, “substring”, “subarray”, “in a row”, “in the last N”.
3. You want the best, the longest, the shortest, or a count of such runs.

If the question says “subsequence” (items in order but not necessarily next to each other) or lets you pick any items, it isn’t a window problem. And if the answer depends on the whole window in a way you can’t update cheaply, a plain running total won’t do; the Advanced section is about exactly those cases.

def moving_average(nums, k):
    total = sum(nums[:k])
    out = [total / k]
    for right in range(k, len(nums)):
        total += nums[right] - nums[right - k]
        out.append(total / k)
    return out

print(moving_average([4, 2, 12, 3, 1, 9, 8], 3))
# [6.0, 5.666666666666667, 5.333333333333333, 4.333333333333333, 6.0]

def count_good_windows(nums, k, threshold):
    need = threshold * k                 # compare sums, not averages: no division, no floats
    total = sum(nums[:k])
    count = 1 if total >= need else 0
    for right in range(k, len(nums)):
        total += nums[right] - nums[right - k]
        if total >= need:
            count += 1
    return count

print(count_good_windows([2, 2, 2, 2, 5, 5, 5, 8], 3, 4))
print(count_good_windows([11, 13, 17, 23, 29, 31, 7, 5, 2, 3], 3, 5))
# 3
# 6

Intermediate: windows that grow and shrink

Fixed and variable windows

Everything so far used a fixed window: the size is given, and both indices move together. Many problems don’t give you a size. They give you a rule and ask how big a window can get while obeying it, or how small it can get while still satisfying it:

• the longest run of characters with no repeats;
• the shortest stretch of a document that mentions every search term;
• the longest run of days where you used at most two kinds of fruit.

These need a variable window. The right index still moves forward one step at a time, adding each new element. The left index moves only when it has to: when the window has broken the rule, left steps forward, removing elements, until the window is valid again.

One template for most of them

Nearly every variable-window solution has this shape:

def variable_window(items):
    state = ...                          # whatever describes the window: a sum, a count, a dict
    left = 0
    answer = ...
    for right, x in enumerate(items):
        add x to state                   # 1. grow on the right
        while state breaks the rule:     # 2. shrink on the left until it's valid again
            remove items[left] from state
            left += 1
        update answer with the window [left, right]   # 3. record
    return answer

That’s pseudocode, not Python. The three numbered steps are the whole pattern, and the problems below differ only in what state is and what “breaks the rule” means. When you meet a new problem, ask those two questions first.

Longest substring without repeating characters

Find the length of the longest run of characters with no character appearing twice. In "abcabcbb" the answer is 3 ("abc"); in "pwwkew" it’s 3 ("wke", not "pwke", which isn’t contiguous).

The state is the set of characters inside the window. The rule is “no repeats”. When a new character is already in the set, shrink from the left until its earlier copy is gone:

def longest_unique(s):
    seen = set()                        # the characters inside the window
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:               # invalid: shrink from the left until it's gone
            seen.remove(s[left])
            left += 1
        seen.add(ch)                    # valid again: grow on the right
        best = max(best, right - left + 1)
    return best

for s in ["abcabcbb", "bbbbb", "pwwkew", "", "dvdf"]:
    print(repr(s), longest_unique(s))
# 'abcabcbb' 3
# 'bbbbb' 1
# 'pwwkew' 3
# '' 0
# 'dvdf' 3

"dvdf" is the case that catches wrong solutions. When the second d arrives, the window is "dv". Dropping everything and restarting from the new d gives "df", length 2, and misses "vdf". Shrinking only until the old d is gone keeps the v.

Go back to the demo above, switch it to Variable: longest without repeats, and type dvdf or pwwkew. Watch the amber cell: it’s the new character waiting while the left pointer clears its earlier copy.

Why a loop inside a loop is still O(n)

The code has a while inside a for. The usual rule of thumb says nested loops cost n × n. Here they don’t, and the reason is the most useful argument in this whole article.

Don’t count the work per iteration. Count it per index, over the whole run. The right pointer steps onto each index exactly once: n moves. The left pointer only ever moves forward, never back, and it can’t pass the right pointer, so it steps past each index at most once: at most n moves. Every unit of work in the function is one of those moves. So the total is at most 2n, however the moves are distributed. Some iterations of the for do no shrinking, a few do a lot, and the sum is bounded anyway. This style of reasoning is called amortized analysis: an expensive step is paid for by the many cheap ones around it.

You can count it instead of trusting it:

import random, string

def longest_unique_counted(s):
    seen, left, best = set(), 0, 0
    moves = {"right": 0, "left": 0}
    for right, ch in enumerate(s):
        moves["right"] += 1
        while ch in seen:
            seen.remove(s[left])
            left += 1
            moves["left"] += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best, moves

random.seed(1)
for n in (1_000, 10_000, 100_000):
    s = "".join(random.choice(string.ascii_lowercase[:6]) for _ in range(n))
    best, moves = longest_unique_counted(s)
    total = moves["right"] + moves["left"]
    print(f"n={n:>7,}: right moves {moves['right']:>7,}, left moves {moves['left']:>7,}, total {total / n:.2f} per character")
# n=  1,000: right moves   1,000, left moves     995, total 2.00 per character
# n= 10,000: right moves  10,000, left moves   9,999, total 2.00 per character
# n=100,000: right moves 100,000, left moves  99,996, total 2.00 per character

With only six letters to choose from, repeats are constant and the left pointer works hard, yet the total never passes two moves per character. A hundred times more input, a hundred times more moves, not ten thousand times.

Jumping instead of crawling

There’s a faster-looking variant. Instead of a set, keep a dictionary from each character to the last index where it appeared. When a repeat arrives, jump left straight past the earlier copy in one step:

def longest_unique(s):
    last = {}                           # character -> the last index we saw it at
    left = 0
    best, best_at = 0, 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1         # jump past the earlier copy in one step
        last[ch] = right
        if right - left + 1 > best:
            best, best_at = right - left + 1, left
    return s[best_at:best_at + best]

for s in ["abcabcbb", "pwwkew", "abba", "tmmzuxt"]:
    print(repr(s), repr(longest_unique(s)))
# 'abcabcbb' 'abc'
# 'pwwkew' 'wke'
# 'abba' 'ab'
# 'tmmzuxt' 'mzuxt'

This version returns the substring itself, which interviewers often ask for as a follow-up. The trap is the last[ch] >= left check. Remove it and "abba" breaks: when the final a arrives, last["a"] is 0, which is already outside the window, and jumping to 1 would move left backwards from 2. A dictionary remembers characters the window has already dropped, so you have to ask whether the remembered copy is still inside.

Both versions are O(n). I write the set version first in an interview, because its correctness is obvious from the template, and mention the jump as an optimization.

Max consecutive ones with k flips

You have a row of bits and may flip at most k zeros to ones. How long can the longest run of ones get? Rephrase it as a window: the longest window that contains at most k zeros. The state is a single number, the count of zeros inside.

def longest_ones(bits, k):
    zeros = 0                           # the window's state: how many 0s it holds
    left = 0
    best = 0
    for right, b in enumerate(bits):
        if b == 0:
            zeros += 1
        while zeros > k:                # more flips than we're allowed: shrink
            if bits[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_ones([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2))
print(longest_ones([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3))
print(longest_ones([0, 0, 0], 0))
# 6
# 10
# 0

The rephrasing is the skill. “Flip at most k” sounds like a search over which zeros to flip. “A window with at most k zeros” is a template you already have.

At most k distinct: fruit into baskets

A row of trees each carries one kind of fruit. You have two baskets, and each basket holds only one kind. Walking left to right from any tree, picking one fruit per tree, how many fruits can you collect before you meet a third kind? That’s the longest window with at most 2 distinct values. The state is a count per value, and the window is invalid when the dictionary holds more than k keys:

from collections import defaultdict

def longest_at_most_k_distinct(items, k):
    counts = defaultdict(int)           # value -> how many times it's in the window
    left = 0
    best = 0
    for right, x in enumerate(items):
        counts[x] += 1
        while len(counts) > k:          # too many different values: shrink
            out = items[left]
            counts[out] -= 1
            if counts[out] == 0:
                del counts[out]         # the key must go, or len(counts) lies
            left += 1
        best = max(best, right - left + 1)
    return best

# Fruit into baskets: two baskets, one kind of fruit per basket.
print(longest_at_most_k_distinct([1, 2, 1], 2))
print(longest_at_most_k_distinct([0, 1, 2, 2], 2))
print(longest_at_most_k_distinct([1, 2, 3, 2, 2], 2))
print(longest_at_most_k_distinct([3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4], 2))
print(longest_at_most_k_distinct("eceba", 2), longest_at_most_k_distinct("aa", 1))
# 3
# 3
# 4
# 5
# 3 2

The del line is where people slip. A count that drops to zero still leaves its key in the dictionary, so len(counts) keeps counting a value that’s no longer in the window, and the loop shrinks too far. Counter behaves the same way: subtracting to zero doesn’t remove the key.

Minimum window substring

So far the windows wanted to be as long as possible. Flip it: find the shortest substring of s that contains every character of t, with repeats counted. For s = "ADOBECODEBANC" and t = "ABC" the answer is "BANC".

The template changes in one place. For longest problems, you shrink while the window is invalid and record after. For shortest problems, you shrink while the window is valid, recording each valid window as you go, because every step left makes it shorter.

The state is a Counter of what’s inside, plus one integer, missing, the number of distinct characters of t not yet fully covered. That integer is the trick: it answers “is the window valid?” in O(1) instead of comparing two counters on every step.

from collections import Counter

def min_window(s, t):
    need = Counter(t)                   # what the window must contain
    missing = len(need)                 # how many distinct characters aren't covered yet
    have = Counter()
    left = 0
    best = (float("inf"), 0, 0)         # (length, start, end)
    for right, ch in enumerate(s):
        have[ch] += 1
        if ch in need and have[ch] == need[ch]:
            missing -= 1                # this character just became fully covered
        while missing == 0:             # valid: record it, then try to make it smaller
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right + 1)
            out = s[left]
            have[out] -= 1
            if out in need and have[out] < need[out]:
                missing += 1            # we just gave up a character we needed
            left += 1
    return s[best[1]:best[2]] if best[0] != float("inf") else ""

print(repr(min_window("ADOBECODEBANC", "ABC")))
print(repr(min_window("a", "a")), repr(min_window("a", "aa")))
print(repr(min_window("aaflslflsldkalskaaa", "aaa")))
# 'BANC'
# 'a' ''
# 'aaa'

missing changes only at the exact moment a character crosses its required count, in either direction, which is why the == and < comparisons are written so carefully. This is the hardest of the classic window problems, and it’s a fair senior interview question.

Counting subarrays: right - left + 1

The third shape counts windows instead of measuring one. How many contiguous subarrays of positive integers have a product below k? For [10, 5, 2, 6] and k = 100 the answer is 8.

Here’s the observation that makes it a window problem. If the window [left, right] has a product below k, then so does every shorter window that also ends at right: [left + 1, right], [left + 2, right], down to [right, right]. Multiplying by fewer positive integers can only make the product smaller. So once the window is valid, it contributes right - left + 1 subarrays at once, all the ones ending at right:

def count_product_below(nums, k):
    if k <= 1:
        return 0                        # positive integers: no product is below 1
    product = 1
    left = 0
    count = 0
    for right, x in enumerate(nums):
        product *= x
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1       # every window ending at `right` that starts at left or later
    return count

print(count_product_below([10, 5, 2, 6], 100))
print(count_product_below([1, 2, 3], 0))
# 8
# 0

I also checked it against the obvious O(n²) version on 2,000 random inputs, and they agreed on all of them. That check is worth the two minutes whenever you write a counting window, because an off-by-one there doesn’t crash; it just gives a slightly wrong number.

Longest, shortest, count

Three shapes of one loop:

def min_len_at_least(nums, target):
    total, left = 0, 0
    best = len(nums) + 1
    for right, x in enumerate(nums):
        total += x
        while total >= target:          # valid: record, then try a shorter one
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return best if best <= len(nums) else 0

print(min_len_at_least([2, 3, 1, 2, 4, 3], 7))
print(min_len_at_least([1, 4, 4], 4), min_len_at_least([1, 1, 1, 1, 1, 1, 1, 1], 11))
# 2
# 1 0

from collections import Counter

def find_anagrams(s, p):
    k = len(p)
    if k > len(s):
        return []
    need = Counter(p)
    window = Counter(s[:k])
    hits = [0] if window == need else []
    for right in range(k, len(s)):
        window[s[right]] += 1           # enters
        window[s[right - k]] -= 1       # leaves
        if window[s[right - k]] == 0:
            del window[s[right - k]]
        if window == need:
            hits.append(right - k + 1)
    return hits

print(find_anagrams("cbaebabacd", "abc"), find_anagrams("abab", "ab"))
# [0, 6] [0, 1, 2]

from collections import Counter

def character_replacement(s, k):
    counts = Counter()
    left = 0
    top = 0                             # the highest count any letter has reached in a window
    best = 0
    for right, ch in enumerate(s):
        counts[ch] += 1
        top = max(top, counts[ch])
        if (right - left + 1) - top > k:     # more than k letters would need replacing
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print(character_replacement("ABAB", 2), character_replacement("AABABBA", 1), character_replacement("ABBB", 0))
# 4 4 3

Advanced: when subtraction isn’t enough

Why a maximum can’t slide like a sum

The running sum works because addition can be undone. When 4 leaves the window, subtract 4, and you’re left with exactly the sum of what remains. Now try that with the maximum. The window [4, 2, 12] has a maximum of 12. Slide it twice: 4 leaves, then 2 leaves, then 12 leaves. Once 12 is gone, what’s the maximum of the rest? The number 12 can’t tell you. You’d have to look at everything that’s left, which is the recounting we were trying to avoid.

In the language of the Expert section, a sum is invertible and a maximum isn’t. Sums, counts, and products of nonzero numbers can be slid by subtraction or division. Maximums, minimums, medians, and “the most common value” need a smarter state.

Three ways to get the sliding maximum

The problem: for every window of size k, report its maximum. For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, the answer is [3, 3, 5, 5, 6, 7].

Brute force takes max of every window: n × k comparisons.

A heap keeps the window’s values in a structure that always knows its largest. Removing an arbitrary element from a heap is awkward, so use lazy deletion: store (value, index), and when you read the top, throw it away if its index has slid out of the window. Each element is pushed once and popped at most once, at a cost of log n each: O(n log n).

A monotonic deque does it in O(n). A deque (double-ended queue, said “deck”) is a list you can add to and remove from at both ends in O(1). The deque holds indices, and their values always decrease from front to back. Two rules keep it that way:

1. When a new value arrives, pop every index at the back whose value is not bigger than it. Those values are smaller than the newcomer and older, so they’ll leave the window first. While the newcomer is in the window, none of them can ever be the maximum again. They’re dead weight.
2. If the index at the front has slid out of the window, pop it from the front.

After both rules, the front is the window’s maximum.

from collections import deque

def window_max(nums, k):
    dq = deque()                        # indices; their values decrease from front to back
    out = []
    for right, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x: # smaller values behind x can never be a maximum again
            dq.pop()
        dq.append(right)
        if dq[0] <= right - k:          # the front has slid out of the window
            dq.popleft()
        if right >= k - 1:
            out.append(nums[dq[0]])     # the front is always the window's maximum
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_max([9, 8, 7, 6, 5], 2), window_max([4], 1))
# [3, 3, 5, 5, 6, 7]
# [9, 8, 7, 6] [4]

Why O(n)? The same argument as before: every index is pushed onto the deque once and popped at most once, from one end or the other. The while loop can pop many indices at one step, but it can’t pop more than were ever pushed.

Step through it. Try a descending run like 9, 8, 7, 6, 5, where nothing is ever popped from the back and the deque fills up, and an ascending run like 1, 2, 3, 4, 5, where every arrival clears the deque:

Here are all three on 200,000 random numbers, measured on my laptop:

import heapq, random, time
from collections import deque

def window_max_brute(nums, k):
    return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]

def window_max_heap(nums, k):
    heap, out = [], []                  # (-value, index): Python's heapq is a min-heap
    for right, x in enumerate(nums):
        heapq.heappush(heap, (-x, right))
        while heap[0][1] <= right - k:  # lazy deletion: drop stale tops only when they surface
            heapq.heappop(heap)
        if right >= k - 1:
            out.append(-heap[0][0])
    return out

def window_max(nums, k):
    dq, out = deque(), []
    for right, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(right)
        if dq[0] <= right - k:
            dq.popleft()
        if right >= k - 1:
            out.append(nums[dq[0]])
    return out

random.seed(11)
nums = [random.randint(0, 1_000_000) for _ in range(200_000)]
for k in (10, 1_000, 10_000):
    timings = {}
    for name, fn in (("brute", window_max_brute), ("heap", window_max_heap), ("deque", window_max)):
        start = time.perf_counter()
        result = fn(nums, k)
        timings[name] = time.perf_counter() - start
        timings[name + "_r"] = result
    same = timings["brute_r"] == timings["heap_r"] == timings["deque_r"]
    print(f"k={k:>6}: same {same}  brute {timings['brute']:6.2f} s  heap {timings['heap'] * 1000:5.0f} ms  deque {timings['deque'] * 1000:4.0f} ms")
# k=    10: same True  brute   0.04 s  heap   156 ms  deque   39 ms
# k=  1000: same True  brute   1.84 s  heap    81 ms  deque   39 ms
# k= 10000: same True  brute  19.60 s  heap    59 ms  deque   40 ms

Look at the first row before you look at the last. With k = 10 the “slow” brute force is the fastest of the three, because max over a slice runs in C while the deque version runs a Python loop. Big-O describes how cost grows, not what it is at your size. At k = 10,000 the brute force takes 20 seconds and the deque still takes 40 milliseconds, because its cost doesn’t depend on k at all. In Python, if k is small and fixed, I’d write the one-liner and move on. If k comes from a user or a config file, the deque.

The sliding median

The median is the middle value when a window is sorted (or the average of the two middle values for an even k). It’s the right summary when a few extreme values would distort an average: one 30-second request in a window of 50-millisecond ones moves the mean a lot and the median not at all.

The simplest correct approach keeps the window sorted at all times. Each slide removes the leaving value with a binary search and inserts the new one in order:

from bisect import bisect_left, insort

def window_median(nums, k):
    window = sorted(nums[:k])           # the window's values, kept in order
    def median():
        mid = k // 2
        return window[mid] if k % 2 else (window[mid - 1] + window[mid]) / 2
    out = [median()]
    for right in range(k, len(nums)):
        del window[bisect_left(window, nums[right - k])]   # leaves: find it by binary search
        insort(window, nums[right])                         # enters: insert in order
        out.append(median())
    return out

print(window_median([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_median([1, 2, 3, 4, 2, 3, 1, 4, 2], 4))
# [1, -1, -1, 3, 5, 6]
# [2.5, 2.5, 3.0, 2.5, 2.5, 2.5]

Finding the position is O(log k), but inserting into or deleting from the middle of a Python list shifts everything after it: O(k) per step, O(n × k) in total. The textbook answer is two heaps: a max-heap holding the smaller half and a min-heap holding the larger half, balanced so their tops are the middle values. Insertion is O(log k), and removal uses the same lazy-deletion trick as the heap maximum. That makes it O(n log k).

So which is faster? I measured both on 200,000 random numbers:

At k = 1,000 the “O(n × k)” sorted list wins, because shifting a thousand pointers is one fast memory move in C, while the heaps pay Python overhead on every push and pop. At k = 100,000 the shifting dominates and the heaps win by thirty times. If your window is a few thousand elements or fewer, the sorted list is shorter, easier to get right, and probably faster. The two-heap version is the Advanced exercise below.

The rule that decides whether a window works at all

Every variable window so far relied on one property without saying it: if a window is valid, every smaller window inside it is valid too (for longest problems), or if a window is valid, every bigger window containing it is valid too (for shortest ones). A substring with no repeats has no repeats in any piece of it. A product below k stays below k if you drop a positive factor. A window that covers all of t still covers it if you add more characters.

That property is called monotonicity, and it’s what makes shrinking safe. When the window breaks the rule, you can move left forward and never need to look back, because any window starting further left and ending at the same place would also break it. Lose the property and the left pointer might skip the answer.

Before writing any variable window, I check this one thing. It’s the difference between a solution that’s correct and one that passes the examples.

When sliding fails: negative numbers

Count the subarrays whose sum is exactly k. With positive numbers a window works: when the sum goes over k, shrink. With negative numbers, it doesn’t. Removing an element from the left can make the sum go up (if the element was negative), so “too big, shrink” stops being safe:

def count_sum_k_window(nums, k):
    """Looks right, and is right only when every number is positive."""
    total, left, count = 0, 0, 0
    for right, x in enumerate(nums):
        total += x
        while total > k and left <= right:
            total -= nums[left]
            left += 1
        if total == k:
            count += 1
    return count

def count_sum_k_prefix(nums, k):
    seen = {0: 1}                       # prefix sum -> how many times we've had it
    running, count = 0, 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

def count_sum_k_brute(nums, k):
    return sum(sum(nums[i:j + 1]) == k for i in range(len(nums)) for j in range(i, len(nums)))

for nums, k in (([1, 2, 3, 1, 1, 1], 3), ([3, 4, -7, 3, 1, 3, 1, -4], 7)):
    print(nums, k, "window:", count_sum_k_window(nums, k), "prefix:", count_sum_k_prefix(nums, k), "truth:", count_sum_k_brute(nums, k))
# [1, 2, 3, 1, 1, 1] 3 window: 3 prefix: 3 truth: 3
# [3, 4, -7, 3, 1, 3, 1, -4] 7 window: 2 prefix: 3 truth: 3

On positive input the window is right. Add a −7 and it misses one, silently. The fix is a different technique: a prefix sum (the running total from the start) plus a hash map counting the prefix sums seen so far. The sum of a subarray is the difference of two prefix sums, so “how many subarrays ending here sum to k” becomes “how many earlier prefix sums equal running - k”, one dictionary lookup. The hash maps article builds this solution step by step as an exercise.

The general rule: negative numbers break sum windows. When you see them, reach for prefix sums. For “shortest subarray with sum at least k” with negatives, the answer combines both ideas, a monotonic deque over the prefix sums, which is about as hard as this family gets.

Exactly K = at most K minus at most K − 1

How many subarrays contain exactly K distinct values? This one resists the template. Grow a window until it has exactly K distinct values, and you can’t tell whether shrinking will keep it at K or drop it to K − 1. “Exactly” isn’t monotone: a valid window can contain invalid smaller ones.

“At most K” is monotone, and counting at-most windows is the right - left + 1 trick from Intermediate. Every subarray with exactly K distinct values has at most K, and isn’t among those with at most K − 1. So:

exactly(K) = atMost(K) − atMost(K − 1)

from collections import defaultdict

def at_most_k_distinct(nums, k):
    """How many subarrays have at most k different values."""
    if k < 0:
        return 0
    counts = defaultdict(int)
    left = 0
    total = 0
    for right, x in enumerate(nums):
        counts[x] += 1
        while len(counts) > k:
            counts[nums[left]] -= 1
            if counts[nums[left]] == 0:
                del counts[nums[left]]
            left += 1
        total += right - left + 1       # windows ending here: [left..right], [left+1..right], ...
    return total

def exactly_k_distinct(nums, k):
    return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)

print(exactly_k_distinct([1, 2, 1, 2, 3], 2), exactly_k_distinct([1, 2, 1, 3, 4], 3))
# 7 3

For [1, 2, 1, 2, 3] and K = 2, the seven are [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2] and [1,2,1,2]. I checked the function against brute force on 2,000 random arrays for K from 0 to 4. Two passes, O(n) each. The same subtraction counts subarrays with exactly K odd numbers, binary subarrays with a given sum, and anything else where “at most” is monotone and “exactly” isn’t.

What the language gives you

The data structures under these windows have costs that depend on the language:

• CPython’s collections.deque is a doubly linked list of blocks, each holding 64 items, so both ends are O(1) and memory stays compact. deque(maxlen=n) is a ready-made fixed window: appending to a full deque silently drops the item at the other end. Indexing into the middle is O(n), so don’t treat a deque as an array.
• Never use list.pop(0) as a queue. It shifts every remaining element. Emptying 200,000 items from the front took 3.28 s with list.pop(0) and 11.7 ms with deque.popleft() on my laptop, about 280 times slower. A time-based window that evicts old events with pop(0) is the classic way this shows up in real code.
• itertools has a sliding_window recipe in its documentation, built on deque(maxlen=n), and Python 3.12 added itertools.batched, which is a tumbling window: batched("ABCDEFG", 3) gives ABC, DEF, G.
• Java’s ArrayDeque is a resizable circular array; it’s the right choice for a monotonic deque, and LinkedList is the wrong one (an object per element).
• Go has no built-in deque. A slice used as a queue with q = q[1:] keeps the whole underlying array alive, including the part before the new start, until an append reallocates it, so a long-running window is better as a ring buffer.

def at_most_odd(nums, k):
    if k < 0:
        return 0
    odd, left, total = 0, 0, 0
    for right, x in enumerate(nums):
        odd += x % 2
        while odd > k:
            odd -= nums[left] % 2
            left += 1
        total += right - left + 1
    return total

def nice_subarrays(nums, k):
    return at_most_odd(nums, k) - at_most_odd(nums, k - 1)

print(nice_subarrays([1, 1, 2, 1, 1], 3), nice_subarrays([2, 2, 2, 1, 2, 2, 1, 2, 2, 2], 2))
# 2 16

import heapq
from collections import defaultdict

def window_median_heaps(nums, k):
    low, high = [], []                  # low: max-heap (negated) of the smaller half; high: min-heap
    delayed = defaultdict(int)          # value -> how many stale copies are still inside a heap
    low_size = high_size = 0            # live elements only, not counting stale ones

    def prune(heap, sign):
        while heap and delayed[sign * heap[0]]:
            delayed[sign * heap[0]] -= 1
            heapq.heappop(heap)

    def rebalance():
        nonlocal low_size, high_size
        if low_size > high_size + 1:
            heapq.heappush(high, -heapq.heappop(low)); low_size -= 1; high_size += 1
            prune(low, -1)
        elif low_size < high_size:
            heapq.heappush(low, -heapq.heappop(high)); high_size -= 1; low_size += 1
            prune(high, 1)

    def add(x):
        nonlocal low_size, high_size
        if not low or x <= -low[0]:
            heapq.heappush(low, -x); low_size += 1
        else:
            heapq.heappush(high, x); high_size += 1
        rebalance()

    def remove(x):
        nonlocal low_size, high_size
        delayed[x] += 1                 # don't search the heap: mark it and drop it when it surfaces
        if x <= -low[0]:
            low_size -= 1
            if x == -low[0]:
                prune(low, -1)
        else:
            high_size -= 1
            if high and x == high[0]:
                prune(high, 1)
        rebalance()

    def median():
        return -low[0] if k % 2 else (-low[0] + high[0]) / 2

    for x in nums[:k]:
        add(x)
    out = [median()]
    for right in range(k, len(nums)):
        add(nums[right])
        remove(nums[right - k])
        out.append(median())
    return out

print(window_median_heaps([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_median_heaps([1, 2, 3, 4, 2, 3, 1, 4, 2], 4))
# [1, -1, -1, 3, 5, 6]
# [2.5, 2.5, 3.0, 2.5, 2.5, 2.5]

Expert: windows over time, streams and networks

Interview windows are over arrays you can index. Real windows are over things that keep arriving: requests, events, packets, sensor readings. The ideas carry over, but three new questions appear. Is the window a number of items or a span of time? When is a window finished, if data can arrive late? And what do you do when you can’t afford to keep every item?

Count-based or time-based?

A count-based window is the last N items: the last 100 requests, the last 20 decisions. A time-based window is everything in the last T seconds: the last minute of requests, the last 3 days. They answer different questions, and they disagree most exactly when it matters:

from collections import deque

class LastNEvents:
    """Count-based: the window is always the most recent n events, however old."""
    def __init__(self, n):
        self.values = deque(maxlen=n)   # a full deque drops its oldest item on append
        self.total = 0
    def add(self, value):
        if len(self.values) == self.values.maxlen:
            self.total -= self.values[0]
        self.values.append(value)
        self.total += value
    def mean(self):
        return self.total / len(self.values)

class LastSeconds:
    """Time-based: the window is everything newer than `seconds`, however many."""
    def __init__(self, seconds):
        self.seconds = seconds
        self.events = deque()           # (timestamp, value), oldest first
        self.total = 0
    def add(self, ts, value):
        self.events.append((ts, value))
        self.total += value
        self.evict(ts)
    def evict(self, now):
        while self.events and self.events[0][0] <= now - self.seconds:
            self.total -= self.events.popleft()[1]
    def mean(self, now):
        self.evict(now)                 # time moves even when no events arrive
        return self.total / len(self.events) if self.events else None

# Response times in ms: a burst of slow requests at t=0..2, then quiet until t=100.
latencies = [(0, 900), (1, 950), (2, 1000), (100, 120)]
count_based, time_based = LastNEvents(3), LastSeconds(60)
for ts, ms in latencies:
    count_based.add(ms)
    time_based.add(ts, ms)
print("at t=100, mean of last 3 events:", round(count_based.mean()))
print("at t=100, mean of last 60 s:   ", round(time_based.mean(100)))
print("at t=200, mean of last 60 s:   ", time_based.mean(200))
# at t=100, mean of last 3 events: 690
# at t=100, mean of last 60 s:    120
# at t=200, mean of last 60 s:    None

The count-based window still remembers a slow burst from a minute and a half ago, because nothing has pushed it out. The time-based window has forgotten it, and at t = 200 it correctly says “no data” rather than repeating old numbers. Two consequences are easy to miss:

• A count-based window has fixed memory; a time-based one doesn’t. The last 60 seconds can hold 3 events or 3 million. If you can’t bound the arrival rate, a time-based window needs a cap, or an approximation (below).
• A time-based window has to evict on reads, not only on writes. mean calls evict(now) first. A window that only evicts when a new event arrives reports stale data forever during a quiet period, which is exactly when an alert most needs to see the quiet.

My rule: use count-based windows for quality questions (“are the last 20 answers good?”), where a slow week shouldn’t mean less evidence, and time-based windows for rate questions (“how many per minute?”), where time is the point.

Tumbling, hopping, sliding and session windows

Stream processors such as Apache Flink and Kafka Streams group an endless stream into windows so they can emit results: counts per minute, averages per hour. There are four standard shapes:

• Tumbling: fixed size, back to back, no overlap. Every event belongs to exactly one window. “Requests per minute” on a dashboard.
• Hopping: fixed size, but a new window starts every hop, smaller than the size, so windows overlap. “A 5-minute average, updated every minute.” An event belongs to size ÷ hop windows.
• Sliding: windows that move with the data rather than the clock. In Kafka Streams, a sliding window aggregation produces a window for the span ending at each event, so it changes only when events arrive or leave.
• Session: no fixed size. A session continues while events keep coming and closes after a gap of inactivity. “One user’s visit”, ending after 30 minutes idle.

Here’s the arithmetic a processor does to place one event, for tumbling and hopping windows:

def assign(ts, size, slide):
    """Which [start, end) windows an event at `ts` belongs to. slide == size is tumbling."""
    last_start = ts - ts % slide
    starts = range(last_start, ts - size, -slide)
    return [(s, s + size) for s in sorted(starts)]

print("tumbling 60 s, event at 125:", assign(125, 60, 60))
print("hopping 60 s every 20 s, event at 125:", assign(125, 60, 20))
# tumbling 60 s, event at 125: [(120, 180)]
# hopping 60 s every 20 s, event at 125: [(80, 140), (100, 160), (120, 180)]

Hopping windows have a cost that sneaks up on you: with a 1-hour window that hops every minute, every event is added to 60 windows. The standard fix is to cut the stream into panes (slices the size of the greatest common divisor of the window size and the hop, here one minute), aggregate each pane once, and build each window by combining its 60 panes. The idea was published by Li, Maier, Tufte, Papadimos and Tucker in 2005 as “No pane, no gain”, and Flink’s SQL window functions use the same slicing approach for tumbling and hopping windows.

Event time, watermarks and late events

On a phone, an event can be created at 12:00:58 and reach your servers at 12:01:30, after a tunnel. Which minute does it belong to? Stream processors distinguish event time (when it happened, a timestamp in the event) from processing time (when it arrived). Windowing by processing time is simple and wrong for anything users care about: the same events give different answers depending on network weather.

Windowing by event time raises a new question: when is the window from 12:00 to 12:01 finished? Events for it might still be on their way. Flink’s answer is a watermark: a claim, carried through the stream, that says “no more events older than time W are expected”. When the watermark passes a window’s end, the window fires. A common strategy is “the highest event time seen, minus the longest delay I’m willing to wait for”, which Flink provides as a ready-made watermark strategy, forBoundedOutOfOrderness. Events that arrive after their window fired are late: Flink can still accept them for an allowedLateness period, re-firing the window with an updated result, and send anything later to a side output instead of dropping it silently. Kafka Streams has no watermarks; it tracks stream time, the highest timestamp seen, and keeps each window open for a grace period after its end.

Here’s that machinery in miniature: 60-second tumbling windows, a watermark 10 seconds behind the newest event, and 30 seconds of allowed lateness:

from collections import defaultdict

def tumbling_counts(events, size, max_delay, lateness):
    """events: (event_time, arrival_order). Watermark = highest event time seen - max_delay.
    A window fires when the watermark passes its end; it accepts updates until end + lateness."""
    counts = defaultdict(int)
    fired = set()
    watermark = float("-inf")
    for ts in events:
        start = ts - ts % size
        end = start + size
        if end + lateness <= watermark:
            print(f"  event at {ts:>3}: window [{start}, {end}) is closed for good -> dropped (late)")
            continue
        counts[start] += 1
        if start in fired:
            print(f"  event at {ts:>3}: late but allowed -> window [{start}, {end}) updated to {counts[start]}")
        watermark = max(watermark, ts - max_delay)
        for s in sorted(counts):
            if s not in fired and s + size <= watermark:
                fired.add(s)
                print(f"  watermark {watermark:>3}: window [{s}, {s + size}) fires with {counts[s]}")

# Event times in the order they arrive. 58, 70, 110 and 12 were held up on the way.
arrivals = [5, 30, 61, 58, 75, 99, 121, 70, 130, 110, 150, 12, 200]
tumbling_counts(arrivals, size=60, max_delay=10, lateness=30)
#   watermark  65: window [0, 60) fires with 3
#   watermark 120: window [60, 120) fires with 4
#   event at 110: late but allowed -> window [60, 120) updated to 5
#   event at  12: window [0, 60) is closed for good -> dropped (late)
#   watermark 190: window [120, 180) fires with 3

The 58 arrived after the 61 but before the watermark passed 60, so it was counted on time. The 70 was out of order too, and still in time. The 110 missed its window’s first result, but was within the allowed lateness, so the window fired again with 5. The 12 was a minute and a half late, and is dropped.

There’s no setting that makes this free. A longer delay means results arrive later for everyone. A shorter one means more late events and more corrections. The design question is which your consumers tolerate better: a dashboard can take corrections; an invoice can’t, so billing windows usually wait longer and fire once.

Aggregates that can’t subtract: two stacks

The deque solved sliding maximum, but it’s specific to max and min. Stream processors need a general answer for any aggregate that combines associatively (in any grouping, the same answer: max, min, sum, greatest common divisor, “merge these two sketches”) and has no inverse.

The classic trick is a queue built from two stacks, where each stack entry also stores the aggregate of itself and everything beneath it. New items go on the back stack. Old items leave from the front stack. When the front stack is empty, the back stack is flipped onto it, recomputing the aggregates in reverse. The window’s aggregate is the front stack’s top aggregate combined with the back stack’s:

import math

class TwoStackWindow:
    """A FIFO window that answers op(all values) in O(1) amortized, for any associative op.
    No inverse needed, so it works for max, min, gcd, and 'sum' alike."""
    def __init__(self, op):
        self.op = op
        self.front = []                 # (value, op of this value and everything above it): the oldest end
        self.back = []                  # (value, op of everything pushed so far into back)

    def push(self, x):
        agg = self.op(self.back[-1][1], x) if self.back else x
        self.back.append((x, agg))

    def pop(self):
        if not self.front:              # flip: move back onto front, rebuilding aggregates
            while self.back:
                x, _ = self.back.pop()
                agg = self.op(x, self.front[-1][1]) if self.front else x
                self.front.append((x, agg))
        return self.front.pop()[0]

    def query(self):
        if self.front and self.back:
            return self.op(self.front[-1][1], self.back[-1][1])
        return (self.front or self.back)[-1][1]

def window_agg(nums, k, op):
    w, out = TwoStackWindow(op), []
    for right, x in enumerate(nums):
        w.push(x)
        if right >= k:
            w.pop()
        if right >= k - 1:
            out.append(w.query())
    return out

print(window_agg([1, 3, -1, -3, 5, 3, 6, 7], 3, max))
print(window_agg([12, 18, 24, 9, 6, 15], 3, math.gcd))
# [3, 3, 5, 5, 6, 7]
# [6, 3, 3, 3]

Each item is pushed once, flipped once and popped once, so the cost is O(1) amortized per item, the same argument as every other window so far. The weakness is the flip: one step occasionally does k units of work, which shows up as a latency spike. Research systems remove it; Tangwongsan, Hirzel and Schneider’s DABA (2017) spreads the flip across later operations to get O(1) in the worst case, not only on average. For a Python service, two stacks is plenty.

Approximate windows

When you can’t keep every event, you approximate. The best-known example sits in front of most APIs: the sliding window counter. It keeps one counter for the current fixed window and one for the previous, and estimates the last full window as previous × (fraction of it still in view) + current. Two integers per caller instead of a log of timestamps, at the cost of assuming the previous window’s traffic was spread evenly.

Two more approximations are worth knowing by name:

• Exponential histograms (Datar, Gionis, Indyk and Motwani, 2002) count the 1s in the last N bits of a stream to within a chosen relative error ε, using about (1/ε) × log² N bits rather than N. They group older events into buckets of doubling size and only ever merge the oldest, so recent detail is kept and old detail is blurred.
• Exponentially weighted moving averages drop the window’s edges entirely: avg = α × new + (1 − α) × avg. Every past value still counts, with weight shrinking geometrically. One number of state, no eviction, and no cliff when an old spike leaves the window. Load averages and many latency trackers work this way.

Rolling hash: a window over a string

Searching for a pattern of length m in a text compares m characters at each of about n positions: n × m. Rabin–Karp (Karp and Rabin, 1987) slides a hash of the window instead. Treat the window’s characters as the digits of a number in some base; when the window moves, subtract the leaving character’s contribution, shift, and add the entering one. Just like the running sum, each slide is O(1). Only when the window’s hash equals the pattern’s do you compare characters:

def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    m = len(pattern)
    if m == 0 or m > len(text):
        return [], 0
    high = pow(base, m - 1, mod)        # the weight of the character about to leave
    want = window = 0
    for i in range(m):
        want = (want * base + ord(pattern[i])) % mod
        window = (window * base + ord(text[i])) % mod
    hits, false_alarms = [], 0
    for left in range(len(text) - m + 1):
        if window == want:
            if text[left:left + m] == pattern:   # equal hashes, so confirm character by character
                hits.append(left)
            else:
                false_alarms += 1
        if left + m < len(text):
            window = (window - ord(text[left]) * high) % mod      # drop the oldest character
            window = (window * base + ord(text[left + m])) % mod  # shift, add the newest
    return hits, false_alarms

print(rabin_karp("abracadabra", "abra"), rabin_karp("aaaaa", "aa"), rabin_karp("hello", "xyz"))

import random
random.seed(4)
text = "".join(random.choice("abcdefghijklmnopqrstuvwxyz ") for _ in range(100_000))
text = text[:20_000] + "window" + text[20_000:60_000] + "window" + text[60_000:]   # plant two real matches
for mod in (101, 1_000_000_007):
    hits, false_alarms = rabin_karp(text, "window", mod=mod)
    print(f"mod {mod:>13,}: {len(hits)} real matches, {false_alarms:,} false alarms")
# ([0, 7], 0) ([0, 1, 2, 3], 0) ([], 0)
# mod           101: 2 real matches, 1,007 false alarms
# mod 1,000,000,007: 2 real matches, 0 false alarms

With a modulus of 101, about one window in a hundred collides with the pattern’s hash by chance, and the confirming comparison saves the answer. With a large prime, collisions all but vanish. The comparison is never optional: equal hashes mean “probably equal”, the same lesson as hash maps.

Rolling hashes matter far beyond string search, because they let you notice the same content even after it shifts. rsync sends a file over a slow link by computing a cheap rolling checksum over every window of the receiver’s copy, so blocks that merely moved are found without being resent; a strong hash confirms each match. The Low-Bandwidth File System (Muthitacharoen, Chen and Mazières, 2001) went further with content-defined chunking: slide a Rabin fingerprint over a 48-byte window and cut a chunk wherever the fingerprint’s low bits match a fixed pattern. Because the cut points depend on content rather than position, inserting a byte at the start of a file changes one chunk, not all of them. Backup and deduplication tools still use the same idea.

TCP: a sliding window over bytes

The window you use most is in TCP. A sender can’t put unlimited data on the wire: the receiver has a finite buffer. So the receiver advertises a receive window, how many more bytes it can take. The sender may have at most that many bytes in flight (sent but not yet acknowledged). As acknowledgements arrive, the left edge of the window moves forward, the right edge follows, and more bytes may be sent:

This is flow control: a slow receiver throttles a fast sender without dropping anything. (The sender also keeps its own congestion window to avoid overloading the network in between, and sends no more than the smaller of the two.) The window size puts a hard ceiling on throughput, because at most one window can be in flight per round trip:

def max_throughput(window_bytes, rtt_seconds):
    """A sender can have at most one window of unacknowledged data per round trip."""
    return window_bytes / rtt_seconds

def needed_window(bits_per_second, rtt_seconds):
    return bits_per_second / 8 * rtt_seconds        # the bandwidth-delay product, in bytes

rtt = 0.100                                          # a 100 ms round trip
print(f"64 KiB window, 100 ms RTT: {max_throughput(65_535, rtt) * 8 / 1e6:.1f} Mbit/s ceiling")
print(f"to fill 1 Gbit/s at 100 ms you need {needed_window(1e9, rtt) / 1e6:.1f} MB in flight")
print(f"window scale needed: shift by {next(s for s in range(15) if 65_535 << s >= needed_window(1e9, rtt))}")
# 64 KiB window, 100 ms RTT: 5.2 Mbit/s ceiling
# to fill 1 Gbit/s at 100 ms you need 12.5 MB in flight
# window scale needed: shift by 8

The TCP header’s window field is 16 bits, so it can’t advertise more than 65,535 bytes. On a 100 ms round trip that caps a connection at about 5 Mbit/s, however fast the link. The window scale option (RFC 7323) multiplies the field by a power of two agreed at connection setup; a shift of 8 covers the 12.5 MB that a 1 Gbit/s, 100 ms path needs. If a long-distance transfer is mysteriously slow on a fast link, a window that’s too small is one of the first things to check.

Reviewing a window in a design

When a design includes “the last N” or “per minute”, these are the questions I ask:

1. Count or time? And if time, what bounds the number of events inside it?
2. Which shape? Tumbling for reports and billing, hopping or sliding for alerts, sessions for user behaviour. Write down the size and the step; a name alone is ambiguous.
3. Whose clock? Event time or processing time, and what happens to an event that’s late. Is it dropped, counted in the next window, or does it correct a published result?
4. Exact or approximate? If approximate, what’s the worst-case error and in which direction?
5. Running total or recompute? A running aggregate is cheaper; recomputing from the source can’t drift. (The production section has an example of each.)
6. What happens at the edges? The first window before it’s full, a quiet period with no events, a restart that loses in-memory state.

def repeated_sequences(dna, k=10):
    code = {"A": 0, "C": 1, "G": 2, "T": 3}
    if len(dna) < k:
        return []
    mask = (1 << (2 * k)) - 1           # keep exactly the last k letters, 2 bits each
    h = 0
    seen, repeated = set(), set()
    for right, ch in enumerate(dna):
        h = ((h << 2) | code[ch]) & mask    # shift in the newest letter; the oldest falls off the top
        if right >= k - 1:
            if h in seen:
                repeated.add(dna[right - k + 1:right + 1])
            seen.add(h)
    return sorted(repeated)

print(repeated_sequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"))
print(repeated_sequences("AAAAAAAAAAAAA"))
# ['AAAAACCCCC', 'CCCCCAAAAA']
# ['AAAAAAAAAA']

In production: windows in ezychat.io

I’m the primary engineer of ezychat.io, a multi-tenant platform where AI and people answer customers on WhatsApp, Instagram, Messenger and web chat. It’s Python (FastAPI and Celery), PostgreSQL and Redis, and production AI runs on Gemini. Windows turn up all over the codebase, and they make different choices: one is approximate and shared through Redis, several are recomputed from the database on every read, one cuts documents for retrieval, and one is described by its comment as a kind of window it isn’t. These are trimmed excerpts from the codebase.

The rate limiter’s two-window estimate

Every limiter in the codebase goes through one function, consume, which implements the sliding window counter from the Expert section. The window arithmetic is five lines:

now = time.time()
window = int(now // window_seconds)
elapsed = (now % window_seconds) / window_seconds
current_key = f"rl:{bucket}:{identity}:{window}"
previous_key = f"rl:{bucket}:{identity}:{window - 1}"

A Lua script inside Redis then computes previous * (1.0 - elapsed) + current and increments atomically. The comment above it explains the choice of an approximate window over an exact one:

It is the standard approximation (the error is bounded by how non-uniform traffic was inside the previous window, under 1% for real traffic) and costs two integers per identity rather than the request log an exact sliding window would need.

That “under 1% for real traffic” is the code’s own claim, not something I measured for this article. The structural point is the one from the Expert design exercise: two integers per caller, no matter how many requests they send.

Overlapping chunks for retrieval

ezychat answers customers from each business’s own documents: price lists, policies, FAQs. To search them, every document is cut into chunks that are embedded (turned into vectors) and stored for retrieval. How you cut them decides what can be found. The chunker’s docstring states the priorities:

Rules, in priority order:

• Headings never emit chunks; they push/pop the breadcrumb stack.
• Paragraphs accumulate under the current breadcrumb up to the target; a question paragraph (ends with “?”) is never split from the paragraph after it — FAQ pairs retrieve as one unit or not at all.
• Tables chunk as header + row group: every chunk repeats the header row, so a product row never retrieves without its column names.
• A single paragraph larger than the hard cap falls back to the 300-token / 50-overlap sliding window, split on word boundaries.

So the sliding window is the fallback, not the main strategy, and I think that’s the right order. Cutting by structure keeps a question with its answer and a table row with its column names. A blind window would cut both in half. The window is only for the case where structure gives you nothing: one enormous paragraph, typically from a PDF that lost its formatting. Here’s the whole fallback:

_CHARS_PER_TOKEN = 4
TARGET_TOKENS = 300
OVERLAP_TOKENS = 50
# Beyond this a text block stops being "one thought" and windows instead.
HARD_CAP_TOKENS = 450

def _window(text: str) -> list[str]:
    """300/50 sliding window over words — the unstructured fallback."""
    words = text.split()
    window_words = TARGET_TOKENS * _CHARS_PER_TOKEN // 5  # ≈ avg 5 chars/word
    overlap_words = OVERLAP_TOKENS * _CHARS_PER_TOKEN // 5
    step = max(1, window_words - overlap_words)
    pieces = []
    for start in range(0, len(words), step):
        piece = " ".join(words[start : start + window_words])
        if piece:
            pieces.append(piece)
        if start + window_words >= len(words):
            break
    return pieces

Read it as a hopping window from the Expert section, over words instead of time. The targets are in tokens, but the window counts words, so the code converts: tokens × 4 characters per token ÷ 5 characters per word gives a window of 240 words, an overlap of 40 words, and a hop of 200. I ran the real function on a 1,000-word paragraph:

pieces = _window(" ".join(f"w{i}" for i in range(1000)))
print(len(pieces), [(p.split()[0], p.split()[-1], len(p.split())) for p in pieces])
# 5 [('w0', 'w239', 240), ('w200', 'w439', 240), ('w400', 'w639', 240), ('w600', 'w839', 240), ('w800', 'w999', 200)]

Three decisions are visible in those few lines:

• Why overlap at all. A sentence that straddles a boundary is split between two chunks, and neither half may match a question about it. With a 40-word overlap, any passage shorter than about 40 words appears whole in at least one chunk. The price is more chunks to embed and store: here 1,160 words for a 1,000-word paragraph, 16% more.
• The break at the end. Without it, the loop would go on producing windows that start inside the last one, and the tail of the paragraph would appear in several chunks that add nothing. The last window is allowed to be short (200 words here) instead.
• Words, not tokens. Splitting on whitespace means a window never cuts a word in half. The token estimate is the same chars ÷ 4 heuristic the module uses everywhere; its docstring says it was calibrated once against the embedding vendor’s tokenizer and is “deliberately not a vendor tokenizer dependency: chunk boundaries only need to be roughly right”.

Each windowed piece also gets the breadcrumb line (the document title and the headings above it) prefixed before embedding, and is tagged {"windowed": True} in its metadata, so a retrieval result can say that it came from the fallback.

How much conversation the model sees

A conversation can run to hundreds of messages, and sending all of them to the model on every turn would be slow and expensive. So the context is a count-based window over the conversation. Two stages use two different windows. The triage step, which decides how hard the turn is, whether it needs the knowledge base and whether a person should take over, reads a short window and then trims it by size:

_HISTORY_WINDOW = 10
_HISTORY_CHARS = 2000

async def _history_text(session, org_id: uuid.UUID, batch: list[Message]) -> str:
    rows = list(
        (
            await session.execute(
                select(Message)
                .where(
                    Message.org_id == org_id,
                    Message.conversation_id == batch[0].conversation_id,
                    Message.created_at < batch[0].created_at,
                )
                .order_by(Message.created_at.desc(), Message.id.desc())
                .limit(_HISTORY_WINDOW)
            )
        ).scalars()
    )
    lines = []
    for message in reversed(rows):
        speaker = "customer" if message.direction == "inbound" else "business"
        lines.append(f"{speaker}: {message_text(message)}")
    return "\n".join(lines)[-_HISTORY_CHARS:]

The reply step uses the same query shape with HISTORY_CAP = 20. Three details make this a window rather than “some recent messages”:

• It’s anchored at the batch, not at now. created_at < batch[0].created_at means the window ends just before the messages being answered, so the new messages are never counted twice, once as history and once as the question.
• Newest first, then reversed. ORDER BY created_at DESC LIMIT 10 is how a database expresses “the last ten”, and reversed puts them back in reading order for the model. The id tie-break makes the window deterministic when two messages share a timestamp.
• Two limits, in the right order. Ten messages could still be very long, so the joined text is cut to the last 2,000 characters. The slice keeps the end, the most recent text, which is the part a triage decision most depends on.

There’s also a rolling summary of each conversation, refreshed after replies on a cheaper model, which travels with a conversation when it’s handed to a person. The model’s own context is the window above.

A rolling score that walks back to zero

Client happiness scoring reads the messages in deal rooms (WhatsApp groups between a business and its client) and turns them into points, bucketed into the organization’s local days. When a room’s rolling score falls into a flagged band, a case can open for someone to follow up. “Recent” is a time-based window of days, three by default and configurable per organization. The module’s docstring calls it “The arithmetic a customer is allowed to dispute”, and the window rule is written for that reader:

The window is a sum of days, not of events. The rolling flag reads the last N daily rows including today, which is what makes the customer’s day-by-day table reproducible with a pencil: each row’s window column is that row plus the N−1 above it.

def window_sum(days: list[DayScore], through: date, window_days: int) -> int:
    """The rolling score on `through`: that day and the `window_days - 1`
    before it.

    Days with no row count as zero rather than being skipped, which is what
    makes the window a *window* — three quiet days after a bad Monday must
    walk the score back to zero, not hold it at Monday's number forever.
    """
    return sum(day.total for day in days if in_window(day.day, through, window_days))


def in_window(day: date, through: date, window_days: int) -> bool:
    """Whether `day` is inside the rolling window that ends on `through`."""
    return window_days >= 1 and through - timedelta(days=window_days - 1) <= day <= through

That docstring is the count-versus-time distinction from the Expert section, decided in business terms. A count-based “last 3 rows” would skip quiet days and keep a bad Monday in the window for as long as nobody wrote anything, which is exactly when a client relationship is cooling. Counting calendar days lets silence do its job.

The other decision is recompute rather than slide. window_sum scans every row for every day it’s asked about, so drawing a room’s whole history is roughly rows × rows checks. A room has one row per day that something happened, so even a year is at most 365 rows and about 133,000 cheap comparisons. The sliding version is faster but not simpler, and the file’s opening says why simple wins here: “A scoring system is trusted exactly as far as it can be re-derived.” I’d make the same call. The exercise at the end of this section writes the linear version anyway, because you should know you could.

“Three bad decisions in the last twenty”

For public comment replies, the AI earns autonomy rung by rung, and can lose it automatically. The demotion rule is a count-based window:

# Three bad decisions in the last twenty drops the channel a rung. Deliberately
# a rate over a recent window rather than a total: an org that has answered ten
# thousand comments should still be caught the week its knowledge goes stale.
BREAKER_WINDOW = 20
BREAKER_BAD = 3

The comment is the argument for windows in general. A lifetime total can’t see a recent change: ten thousand good replies would bury twenty bad ones. A time window would be the wrong shape too, because a channel that replies twice a week would rarely have enough decisions in any week to judge. “The last 20 decisions” always holds the same amount of evidence, however busy the channel is. The query is the window:

recent = (
    await session.execute(
        select(CommentThread.draft_decision)
        .where(
            CommentThread.org_id == org_id,
            CommentThread.channel_id == channel_id,
            CommentThread.draft_decided_at.is_not(None),
        )
        .order_by(CommentThread.draft_decided_at.desc())
        .limit(BREAKER_WINDOW)
    )
).scalars().all()
if len(recent) < BREAKER_WINDOW:
    # Too little to judge. Demoting on three of four would fire on a
    # channel somebody is still setting up.
    return None

Two choices here go against the textbook, on purpose. First, it doesn’t keep a running count. The module’s docstring says so directly: “Nothing here is a counter. Every number is derived by counting comment_threads.draft_decision rows. A rolling counter drifts from the events it summarises, and the first time the two disagree nobody can say which is right.” A sliding counter in Redis would be faster, and would be a second source of truth. When the window is 20 rows behind an index, recomputing costs nothing worth saving. Second, a window that isn’t full doesn’t judge. That’s the “first window before it’s full” edge from the design checklist, decided explicitly: three bad decisions out of four is not the same evidence as three out of twenty.

A rolling 24 hours, not a calendar day

Deal rooms are WhatsApp groups that a business’s own number opens, and opening too many too fast can get a number restricted by WhatsApp. The daily allowance is checked against a sliding window, and the docstring explains why it isn’t a tumbling one:

A rolling 24 hours, not a calendar day.

WhatsApp’s patience does not reset at anyone’s midnight, and a calendar day would need the org’s timezone to be right — which would make the ban guard depend on a setting somebody can get wrong. A rolling window is stricter at the boundary and needs no configuration to be correct.

“Stricter at the boundary” is the fixed-window burst problem from the rate limiter article, seen from the other side: a calendar day allows a full day’s allowance at 23:59 and another at 00:01. The query is just DealRoom.created_at >= now - timedelta(days=1). Meta’s own publishing limits are rolling windows too, and the adapters record them as Meta documents them: 50 API-published posts per Instagram business account per rolling 24 hours, and 30 API-published Reels per Facebook Page per rolling 24 hours.

Hopping on purpose: the pre-flight sweep

Scheduled social posts get a warning about an hour before their slot if something would stop them publishing: a disconnected account, an expired token, a video that never finished processing. A periodic job finds them, and the obvious version has a gap. The schedule entry explains it:

# Pre-flight for scheduled posts (cycle 2, C1d). Hourly, against a
# 100-minute horizon: a 60-minute window checked every 60 minutes leaves
# slots falling between two ticks unchecked, and the whole value of this
# is that the warning arrives while there is still time to act.
"preflight-scheduled-posts": {
    "task": "ezychat.publishing.pipeline.preflight_scheduled_posts",
    "schedule": 3600.0,
},

The sweep looks at posts scheduled more than 5 and at most 100 minutes ahead. In Expert terms it’s a hopping window: 95 minutes wide, hopping every 60, so consecutive windows overlap by 35 minutes. A window exactly as wide as the hop is a tumbling window, and it only works if every run happens exactly on time; any delay in the scheduler leaves an unchecked gap. Making the window wider than the hop buys tolerance, and costs something every hopping window costs: some posts are seen by two runs. The notification’s dedupe key handles that:

def _preflight_dedupe(payload: dict[str, Any]) -> str:
    # Keyed on the slot, not the post. Rescheduling to a new time is a new
    # deadline and deserves a new warning; the same slot checked twice by an
    # overlapping sweep is not.
    return f"post.preflight_failed:{payload.get('post_id')}:{payload.get('scheduled_at')}"

Overlap plus a dedupe key is the general recipe for periodic jobs that must not miss anything: make the windows overlap so delays can’t open gaps, and make the effect idempotent so the overlap can’t double up.

A window the comment calls sliding

The model client has a circuit breaker: after enough failures from one model in a short time, it stops sending to that model for a while and fails over to the backup. The tuning comment says:

# Breaker tuning: >= _CB_THRESHOLD availability failures inside a
# _CB_WINDOW_S sliding window opens the circuit for _CB_COOLDOWN_S. When
# every candidate's circuit is open, `generate_with_failover` still sends
# one probe to the last candidate — the breaker is a load-shedding
# optimization, never a hard gate that could refuse all replies.
_CB_WINDOW_S = 60
_CB_THRESHOLD = 5
_CB_COOLDOWN_S = 30

And here’s the counting:

async def record_failure(self) -> None:
    try:
        redis = get_redis()
        count = await redis.incr(self._fail_key)
        if count == 1:
            await redis.expire(self._fail_key, _CB_WINDOW_S)
        if count >= _CB_THRESHOLD:
            await redis.set(self._open_key, "1", ex=_CB_COOLDOWN_S)
            await redis.delete(self._fail_key)
    except Exception:
        pass

async def record_success(self) -> None:
    try:
        await get_redis().delete(self._fail_key)
    except Exception:
        pass

With this article’s vocabulary, that isn’t a sliding window. The expiry is set only by the first failure, so the window is 60 seconds anchored at the first failure of a run, a fixed window that starts when trouble starts rather than on the clock. And because every success deletes the key, what it really counts is five failures with no success between them, within a minute of the first. That’s a reasonable rule for a breaker (a model that’s answering at all shouldn’t be cut off), but it’s a different rule from “five failures in any 60 seconds”, which would catch a model failing every other call.

The code also uses the separate INCR then EXPIRE that the rate limiter replaced, because a lost EXPIRE there could leave a counter that never expires. Here the same failure is bounded: the next success or the opening of the breaker deletes the key, so the worst case is a breaker that opens a little early, not a model locked out forever. Throttling errors are kept out of the count entirely, since a model telling you to slow down isn’t down.

I’m including it because the mismatch is in the words, not the code, and that kind of window bug is easy to miss in review. “Sliding window” gets written on anything with a time limit. When you review one, read the expiry and the reset paths, and write down which of the four shapes it actually is.

What production adds to the textbook

• Count or time is a product decision. Days for a score a customer can dispute, decisions for a quality breaker, a rolling 24 hours for a third party’s patience. Each comment above argues for its choice in business terms, and each argument would fail for the other kind.
• Recompute when you can, slide when you must. Three of these windows are a SQL query with ORDER BY ... LIMIT or a date filter, recomputed on every read, because the source of truth is already indexed and a second running copy could drift. The one that slides is the rate limiter, which runs on every request and couldn’t afford a query.
• Overlap needs idempotency. Overlapping chunks cost storage; overlapping sweeps cost duplicate work. Both are worth it, and both need something (a break, a dedupe key) that stops the overlap from multiplying.
• The edges are where the decisions are. A window that isn’t full yet, a quiet period, a last chunk that’s short. Every window above handles at least one of those explicitly, and the comments explain why.

from datetime import date, timedelta

def series_sliding(rows, window_days):
    """One pass: rows enter on the right, leave once they're window_days or more behind."""
    ordered = sorted(rows)
    out, total, left = [], 0, 0
    for day, value in ordered:
        total += value
        while ordered[left][0] <= day - timedelta(days=window_days):
            total -= ordered[left][1]
            left += 1
        out.append((day, total))
    return out

rows = [(date(2026, 10, 5), -6), (date(2026, 10, 6), 1), (date(2026, 10, 9), 2), (date(2026, 10, 10), -1)]
for (day, value), (_, window) in zip(sorted(rows), series_sliding(rows, 3)):
    print(day, f"{value:>3}", f"window {window:>3}")
# 2026-10-05  -6 window  -6
# 2026-10-06   1 window  -5
# 2026-10-09   2 window   2
# 2026-10-10  -1 window   1

Cheat sheet