Deques and Expiring Windows

1. When to reach for a deque

Something arrives over time, and old things stop mattering.

That’s the tell, and it’s worth attaching to the word “deque” directly, because the shape is easy to describe in English without reaching for the structure. If you catch yourself saying “pop the oldest, push the newest,” that’s this.

Phrasings that mean the same thing:

• “in the last 60 seconds”
• “the most recent K items”
• “at any point,” over a stream
• a fixed-size buffer that overwrites the oldest

Not the two-pointer kind of sliding window, which is a separate pattern over a fixed array.

2. What it is

A doubly ended queue. O(1) at both ends, O(n) in the middle.

from collections import deque

dq = deque()
dq.append(x)       # add right
dq.appendleft(x)   # add left
dq.pop()           # remove right
dq.popleft()       # remove left
dq[0]              # oldest, O(1)
dq[-1]             # newest, O(1)

A plain list already gives O(1) at the right end, so append and pop are fine on a list. What a list can’t do is the left end: lst.pop(0) is O(n) because every remaining element shifts down.

So reach for a deque exactly when you need the left end. Which is precisely the shape above: new things arrive on the right, old things expire from the left.

deque(maxlen=N) auto-evicts from the far end when full, which is a fixed-size buffer in one line. It costs you O(1) indexing in the middle, so it doesn’t suit “get the i-th oldest.”

3. The expiry loop

The canonical operation. Everything older than the cutoff leaves the front:

while dq and dq[0] < timestamp - window:
    dq.popleft()

The emptiness check goes first, inside the while. Python evaluates and left to right and short-circuits, so dq being falsy stops it before dq[0] runs.

This is the single most expensive mistake I make. Three shapes of it, all the same bug:

while dq[0] < cutoff and dq:        # index runs first, IndexError
if dq:                              # guards entry, but the LOOP is what empties it
    while dq[0] < cutoff:
        dq.popleft()
if self.users:                      # checks the dict, not the deque inside it
    while self.users[uid][0] < cutoff:

The loop is what empties the container, so the check has to be re-evaluated every iteration. Guarding before the loop only checks the first one.

4. Cost of the expiry loop

A single call can pop many items, so one call is not O(1). What makes it fine:

Each item is appended exactly once and popped at most once. So the total popping across the entire run is bounded by the number of appends. Amortized, it’s O(1) per item.

Say it as two numbers when asked: a single call is O(k) where k is what expired, and it’s amortized O(1) per item.

That argument is what licenses lazy cleanup generally, and it’s the same one behind lazy deletion in a heap: don’t do work eagerly if the work is bounded by what you already paid for on the way in.

5. Worked example: a rate limiter

RateLimiter(max_requests, window_seconds), and allow(user_id, timestamp) returns whether the request is permitted, allowing at most max_requests in any window_seconds period.

from collections import defaultdict, deque

class RateLimiter:
    def __init__(self, max_requests, window_seconds):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self.user_requests = defaultdict(deque)

    def allow(self, user_id, timestamp):
        dq = self.user_requests[user_id]
        while dq and dq[0] < timestamp - self.window_seconds:
            dq.popleft()
        if len(dq) < self.max_requests:
            dq.append(timestamp)
            return True
        return False

Expire first, then count. The count after expiry is exactly the number of requests inside the window, so no separate counter is needed.

Binding dq = self.user_requests[user_id] once at the top is worth doing. Repeating self.user_requests[user_id] three times per line is where the “which container am I checking” confusion comes from.

6. Deleting entries for users who stopped arriving

The dict above never shrinks. A million users who each made one request days ago still have an entry, holding an empty deque.

Scanning all users on every call fixes it and costs O(users) per request, which throws away the reason the per-user structure was cheap.

The cheaper version: keep a second deque of user IDs, pushed whenever a user is recorded. On each call, pop a bounded number from its front, and for each one either delete the entry or put the user back at the back of the queue:

def _cleanup(self, timestamp):
    if not self.cleanup_queue:
        return
    uid = self.cleanup_queue.popleft()
    dq = self.user_requests[uid]
    if not dq or dq[-1] < timestamp - self.window_seconds:
        del self.user_requests[uid]      # nothing live, drop it
    else:
        self.cleanup_queue.append(uid)   # still active, check again later

Two things that are easy to get wrong:

• Re-append to the back, not the front. appendleft puts the same user at the head and the next call pops them again, so the queue never advances past its first live user.
• An empty deque still has to be deleted. If a user’s timestamps all expired through the normal path, their entry exists holding an empty deque. Dropping them from the cleanup queue without deleting the entry is exactly the leak this was meant to fix.

The user ID appears in the cleanup queue multiple times, once per recorded request. That’s fine: duplicates get popped, find the entry already deleted or still live, and cost O(1) each.

7. Monotonic deques

When the question asks for the maximum in the window rather than the count, expiry alone isn’t enough, because removing the maximum leaves you scanning for the next one.

The fix is to keep the deque monotonic: on arrival, pop smaller values off the back before appending, because a newer larger value makes them permanently irrelevant. They expire sooner and they’re smaller, so they can never be the answer.

What’s left decreases front to back, the front is the current maximum, and expiry still happens at the front by timestamp. Both ends live, doing different jobs, which is the case where nothing simpler than a deque works.