Queue over a time window

37 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A website counts how many times it was visited in the last 5 minutes (300 seconds). Visits arrive at seconds 1, 2, 3, 300, 302, and at various moments someone asks "how many hits in the last 300 seconds?" At second 4 the answer is 3. At second 301 the hit at second 1 is now too old (301 − 300 = 1, and the window is the 300 seconds ending now, so second 1 is just outside), and the answer is 3 again: seconds 2, 3 and 300.

By hand you keep a list of every visit time, and for each question you walk the whole list and count the ones that are recent enough. If a busy site has a million visits, every question walks a million entries, and most of them are ancient and will never count again.

The waste is clear: old visits never come back. Once a visit is outside the window it is outside forever, because time only moves forward.

Build the structure, one piece at a time

Piece 1: a queue. A queue is a line at a counter: new people join at the back, and the person served is the one at the front. Add to the back, remove from the front, nothing else. We will store the visit times.

Piece 2: add at the back. Each visit is appended at the back. Because visits arrive in time order, the queue is automatically sorted: oldest at the front, newest at the back.

Piece 3: trim the front. When a question arrives at time t, look at the front. While the front time is ≤ t − 300, it is too old: remove it. Stop at the first time that is recent enough. Everything behind it is even more recent, so no further checks are needed.

Piece 4: answer. The answer is the length of the queue.

Why it is correct

The invariant: after a question at time t is answered, the queue holds exactly the visits with time > t − 300, in increasing order.

Order: visits are appended in time order and removals only happen at the front, so the queue stays sorted. Exactness: the trimming loop removes from the front while the front is too old; it stops at the first recent visit, and since the queue is sorted every later visit is also recent. Nothing recent is removed, nothing old remains.

answer(t) = number of visit times v with t − 300 < v ≤ t = length of the queue

A question at a later time can only make more entries old, never fewer, which is why removing permanently is safe.

Why it is fast

Each visit is appended once and removed at most once. A single question may remove many entries, but across all questions the total number of removals cannot exceed the number of visits. So over m visits and q questions the total work is at most m + m + q.

total work ≤ 2m + q, so each operation costs O(1) on average (amortised)

"Amortised" means one call might be slow after a long quiet period, but the average over a sequence is constant. Compare with walking a million entries per question.

If the counts can be huge, store (time, count) pairs instead of one entry per visit; a visit at the same second as the back entry just increments its count.

How to recognise it in an interview

Listen for "in the last W seconds", "rate limit", "moving average of the last k values", "recent calls". Anything with a time or count window that only moves forward is this pattern. Say: "Events only age out, so a queue with trimming at the front answers each query in amortised constant time."

Design Hit Counter is the example above. Logger Rate Limiter keeps, per message, the last time it was printed and refuses if the gap is under 10 seconds, the same idea with a map instead of a queue. Moving Average from Data Stream is a queue of the last k values with a running sum, so each average is one subtraction and one division.

02The idea in one line

Push timestamps; pop from the front while they fall outside the window.

Reach for it when: Hit counters, rate limiters, moving averages, recent requests.

Cost: O(1) amortised per event.

03The walk-through, step by step

The video works one example: Hit counter with 300 s window. These are its captions in order, so you can follow without the video or check a step you missed.

1. Keep every hit in a queue; drop fronts older than t − 300
2. hit(1): append 1
3. hit(2): append 2
4. hit(3): append 3
5. getHits(4) = queue length = 3
6. hit(300): append 300
7. getHits(300) = queue length = 4
8. getHits(301): 1 ≤ 1, pop from the front
9. getHits(301) = queue length = 3
10. hit(302): append 302
11. getHits(303): 2, 3 ≤ 3, pop from the front
12. getHits(303) = queue length = 2
13. Each timestamp enters and leaves once: O(1) amortised per call

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Queue & Deque: Monotonic deque window max, Queue from two stacks.