Sliding Time Window: Deque, Ring Buffer and Buckets

Many design problems only care about recent events: hits in the last 5 minutes, prints in the last 10 seconds, tokens that have not expired, the average of the last n values. The trap is a dict that remembers everything forever, which is a memory leak. The pattern is to keep only the window, using one of three structures: a deque you prune from the front, a fixed ring buffer that overwrites itself, or coarse time buckets.

The idea#

Events arrive with non-decreasing timestamps, so anything that falls out of the window falls out at the old end. That gives three options.

Why the deque is fast: each event is appended once and popped once, so pruning is amortized $O(1)$ per event, even if one call pops many.

Why the ring buffer needs no cleanup: slot t % W is reused every W seconds. Each slot remembers which second it holds. On a hit, if the stored second differs, the slot is reset and reused. Old data is overwritten, so there is no background cleanup thread and memory never grows.

How to spot it#

The problem talks about time or count windows over a stream.

• "in the past 300 seconds", "within the last 10 seconds", "per minute"
• "at most K requests per window", "should this message print"
• "expires after ttl", "count unexpired tokens"
• "moving average of the last size values"
• timestamps are given in non-decreasing order (so the oldest is always at the front)

Template#

Two building blocks cover most problems. First, the operations of a ring-buffer counter: hit is $O(1)$, get_hits is $O(W)$, and memory is fixed at W slots.

init(W):
    times = W zeros                  # which second each slot belongs to
    counts = W zeros
hit(t):
    i = t % W
    if times[i] != t:                # slot holds an old second: reuse it
        times[i] = t; counts[i] = 0
    counts[i] += 1
get_hits(t):
    return the sum of counts[i] over slots where t - times[i] < W

Second, a deque of expiries with tombstones: stale entries you leave in place instead of deleting. Renewing a key appends a new entry, and the old one becomes a tombstone. The dict is the source of truth, and a stale entry is checked against it only when it reaches the front.

init(ttl):
    expiry = empty dict              # key -> expiry time (the truth)
    log = empty deque                # (expiry, key), sorted: time only grows
add_or_renew(key, now):
    expiry[key] = now + ttl
    append (now + ttl, key) to log   # any older entry is now a tombstone
count_live(now):
    while log is not empty and its front has expired:
        exp, key = pop from the left of log
        if expiry[key] == exp: delete key from expiry   # skip tombstones
    return the size of expiry

A heap of expiries would also work, but every expiry is now + ttl with now only growing, so entries arrive already sorted. A deque gives $O(1)$ appends instead of $O(\log n)$ pushes. That is the key observation: when keys arrive in order, you don't need a heap.

Ring buffer or binary search?#

Before you commit to a ring buffer, compare it with its main alternative: a sorted list of timestamps plus binary search, covered in Sorted Timestamps + Binary Search. That approach answers any window size in $O(\log n)$, but stores every timestamp unless you prune.

Choose the ring buffer when memory and stability matter most, and binary search when lookup speed and flexible windows matter most.

Rate limiters: three algorithms on one trace#

Rate limiters are the most common place these structures show up. A per-user limiter of limit requests per window seconds can be built three ways.

• Fixed window: window_id = t // window plus a counter. Two integers, $O(1)$ space. When window_id changes, reset the counter.
• Sliding window log: a deque of accepted timestamps. Prune the front, then accept if fewer than limit remain. $O(\text{limit})$ space per user, amortized $O(1)$ time.
• Token bucket: a float tokens, refilled at limit / window tokens per second since the last call, capped at limit. Accept if at least one token is left. $O(1)$ space.

The fixed window has a boundary burst: with 2 per 60 s, requests at 58, 59, 60 and 61 are all accepted, because 60 starts a new window. That is 4 requests in 4 seconds. The sliding log rejects 60 and 61.

To compare all three side by side, here is one trace with limit 2 per 60 seconds (the log treats an entry exactly 60 s old as expired):

The sliding log is the "honest" one: at t = 50 there were 2 requests in the last 60 seconds. The token bucket is "forgiving": it refills continuously, so evenly spread requests get slightly more throughput, while a concentrated burst is still capped at limit. The full design (per-user state, retry-after, locking, distributed limits) is in the Rate Limiter LLD.

Pitfalls#

Each of these costs you memory, speed or correctness.

• Unbounded dicts. "Last time seen" maps grow forever unless something removes old keys.
• Off-by-one at the window edge. Decide whether an event exactly window seconds old is inside, and use < or <= to match. Read the problem's exact range.
• list.pop(0) instead of deque.popleft(). The list version is $O(n)$ per pop.
• Deleting a renewed key. When you pop an old entry, check that the dict still holds that same time before deleting.
• Pruning in only one method. Every method that reads the state must prune first, or expired data leaks into answers.
• Late events in a ring buffer. A late hit can land in a slot that a newer second has already reset, so the ring buffer assumes roughly in-order data.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Logger Rate Limiter and Design Hit Counter.

• 359. Logger Rate Limiter
• 346. Moving Average from Data Stream
• 362. Design Hit Counter
• 622. Design Circular Queue
• 1797. Design Authentication Manager

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Keep only the window. Anything that stores all history needs a pruning plan.
• A deque of in-order events prunes in amortized $O(1)$: each item enters and leaves once.
• A ring buffer of [second, count] gives fixed memory with no cleanup thread; coarser buckets shrink it further.
• In-order timestamps make a deque enough; a heap is only needed when keys arrive out of order.
• Tombstones (leave stale entries, validate against the dict at the front) make updates $O(1)$.
• Fixed window, sliding log and token bucket trade memory against accuracy at window boundaries.