Number of Recent Calls: Queue-Based Sliding Window

You are building a system that tracks how many requests have arrived in the last 3000 milliseconds. Each new request comes with a timestamp, and you need to report how many requests (including the current one) fall within the window [t - 3000, t].

This is LeetCode 933: Number of Recent Calls, an easy problem that introduces the queue-based sliding window pattern. You implement a RecentCounter class with a single method ping(t) that records a new request at time t and returns the count of requests in the inclusive range [t - 3000, t]. Timestamps are guaranteed to be strictly increasing.

Why brute force is wasteful

The simplest approach is to store every timestamp in a list and, on each ping, scan the entire list to count how many values fall within the window.

class RecentCounter:
    def __init__(self):
        self.pings = []

    def ping(self, t):
        self.pings.append(t)
        count = 0
        for p in self.pings:
            if p >= t - 3000:
                count += 1
        return count

This works, but it gets slower over time. The list grows with every call, and you scan all of it every time. If there have been n pings total, each ping call takes O(n) time. After thousands of calls, you are scanning thousands of old timestamps that you already know are expired. You never remove anything, so you keep paying for data you no longer need.

The key insight: use a queue

Once a timestamp falls below t - 3000, it will never be relevant again. Future pings will have even larger t values, which means the window only moves forward. An expired timestamp stays expired forever.

This is a perfect fit for a queue (specifically, a deque). You add each new timestamp to the back. Then you remove timestamps from the front as long as they are outside the window. What remains in the queue is exactly the set of timestamps in [t - 3000, t], and its length is your answer.

Clean solution

from collections import deque

class RecentCounter:
    def __init__(self):
        self.queue = deque()

    def ping(self, t):
        self.queue.append(t)
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

Here is what each piece does:

1. self.queue = deque() initializes an empty double-ended queue. A deque supports O(1) append and popleft, which is exactly what you need.
2. self.queue.append(t) adds the new timestamp to the back of the queue.
3. while self.queue[0] < t - 3000 checks if the oldest timestamp is outside the current window. If it is, remove it with popleft(). Repeat until the front of the queue is within range.
4. return len(self.queue) returns the count of timestamps still in the queue, which is the number of recent calls.

Notice there is no if check before accessing self.queue[0]. That is safe because you just appended t, so the queue is guaranteed to have at least one element. The while loop condition will fail immediately if the only element is t itself (since t is never less than t - 3000).

Walking through it step by step

Let's trace through the calls ping(1), ping(100), ping(3001), ping(3002) to see the queue evolve.

The boundary case at step 3 is worth noting. When t = 3001, the window is [1, 3001]. The value 1 is exactly equal to t - 3000 = 1, so it is not less than the cutoff, and it stays. But at step 4, when t = 3002, the cutoff becomes 2, and now 1 < 2, so it gets removed. The strict less-than comparison (< instead of <=) matches the inclusive window definition.

Complexity analysis

Each timestamp is appended once and removed at most once across all calls. Even though a single ping might remove multiple old entries from the front, the total number of removals across all calls is bounded by the total number of appends. This gives O(1) amortized time per call.

The space is bounded by the number of pings that can fit in a 3000ms window. In the worst case (pings arriving at every integer timestamp), that is 3001 entries. In practice, it depends on the call frequency.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Queue / deque as a sliding window container

The pattern of maintaining a queue where you add to the back and remove from the front to keep a sliding window of valid elements:

queue = deque()
for item in stream:
    queue.append(item)
    while queue and should_remove(queue[0]):
        queue.popleft()
    # queue now contains only valid items

In Number of Recent Calls, the removal condition is queue[0] < t - 3000. In Sliding Window Maximum, a similar deque tracks indices of candidates. In Moving Average from Data Stream, the queue holds the last k values. The skeleton is the same: append, remove stale entries from the front, read the answer from the queue.

2. Amortized O(1) removal

The insight that each element enters and leaves the queue exactly once makes the total work linear, even though individual operations might remove multiple elements. This amortized argument is the same one behind two-pointer sliding windows, stack-based problems like Next Greater Element, and dynamic array resizing.

Edge cases

Before submitting, make sure your solution handles these:

• First ping: the queue is empty before the call. After appending, the queue has one element, and the while loop does not execute. Returns 1.
• All pings within 3000ms of each other: nothing ever gets removed. The queue grows with each call. Each call returns the total number of pings so far.
• Large gap between pings: if the next ping is more than 3000ms after the previous one, all old entries get removed. For example, ping(1) then ping(5000). After the second call, the queue contains only [5000]. Returns 1.
• Boundary value: ping(1) then ping(3001). The window is [1, 3001]. Since 1 is not less than 3001 - 3000 = 1, it stays. Returns 2. But ping(3002) would remove it.
• Rapid successive pings: ping(1), ping(2), ping(3), ..., ping(3001). All 3001 values remain in the queue because they all fall in [1, 3001].

The queue-based solution handles all of these without special-case logic.

From understanding to recall

You have read the queue solution and it makes sense. One deque, one while loop, one return statement. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: using < instead of <= in the while condition, remembering that deque supports popleft() in O(1) while a regular list does not, and knowing that the queue is guaranteed non-empty after the append so you do not need a length check. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the queue-based sliding window from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "count events in a time window" and the code flows out without hesitation.

The queue/deque sliding window pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Sliding Window Pattern - The general technique of maintaining a window over a sequence with two pointers or a deque
• Design Circular Queue - Building a queue with fixed capacity using a circular buffer
• Implement Queue Using Stacks - Simulating queue operations using two stacks, another design problem

CodeBricks breaks the number of recent calls LeetCode problem into its queue-based sliding window and amortized removal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sliding window design question shows up in your interview, you do not think about it. You just write it.