How many requests arrived in the recent window?

Stacks and queues Junior Python 3.13+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank so old times leave the window.

Python 3.13
from collections import deque
w = 3000
recent: deque[int] = deque()
out = []
for t in [1, 100, 3001, 3002]:
    recent.append(t)
    while recent[0] < t - w:
        ____
    out.append(len(recent))
print(out)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A recent.popleft()

Right: the oldest time sits at the front of the queue.

At t = 3002 the request at time 1 falls out of the window, which is why the last count is 3.

Why not the others?
  • B recent.pop(). That removes the newest time, which is still inside the window.
  • C recent.clear(). That drops times that are still inside the window.

30-second answer

Keep a queue of recent request times. For each new time t, append it and drop times from the front while they are older than t - w. The queue length is the answer for t. Each time enters and leaves once: O(n) time, O(w) space at most.

Practise saying it · 30 s. No recording, just a timer

Explain counting requests in a recent window.

Say your answer out loud, then check which of these points you covered:

  • Queue of times
  • Drop from the front
  • O(n) total

Deep dive

Increasing input times are what make the front of the queue always the oldest.

This is a sliding window over time instead of over positions.

For out-of-order times you need a sorted structure or bucketed counts.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from collections import deque


def recent_counts(times: list[int], w: int) -> list[int]:
    recent: deque[int] = deque()
    counts = []
    for t in times:
        recent.append(t)
        while recent[0] < t - w:
            recent.popleft()
        counts.append(len(recent))
    return counts

Common mistakes

  • Using list.pop(0) for the queue, which is O(n) per drop.
  • Off-by-one at the window edge: the window [t - w, t] includes t - w.

Senior take & follow-ups

Point out why the queue's front is always the oldest time; it is what lets you drop in O(1).

Follow-up questions

Think of your answer first, then open the hint.

  1. How would a rate limiter use this?

    Show hint

    Reject a request when the count for its time would exceed the limit.

  2. What if you need counts for many users?

    Show hint

    One queue per user in a dict, dropping idle users periodically.

Similar on Backend: Background job queues A job queue hands work out in arrival order, like the deque here; the backend version adds durability, retries and many consumers.

What each operation costs: Stack · Queue · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.