933. Number of Recent Calls
Easy · solved 2026-10-04 · Open on LeetCode
queuedesigndata-stream
Time O(1) amortized per ping · Space O(3001)
How to get there
The oldest ping is the first to expire
1. Answer a few pings by hand. Pings arrive at 1, 100, 3001, 3002. At 3001 the window is [1, 3001], so all three count. At 3002 the window is [2, 3002]: the ping at 1 has fallen out, and it will never count again, because later windows only start later.
2. Find what must be remembered between pings. Every ping still inside the window, since each later call needs to know how many there are. Pings outside it can be forgotten for good.
3. Notice which pings leave, and in what order. Times strictly increase, so pings arrive oldest first, and the oldest is always the first to fall out of the window. First in, first out: that is a queue. Each ping joins at the back, and expired pings leave from the front.
4. Answer with the queue’s length. Once the expired pings are gone, everything in the queue lies in [t − 3000, t], so its length is the answer.
5. Check the cost. A single call may drop many pings, but each ping is added once and dropped at most once, so every call costs O(1) on average. Times are whole milliseconds and strictly increasing, so at most 3001 pings fit in a window, and the queue never grows past that.
The reusable recipe: for “how many events in the last T”, keep the events in a queue and drop from the front everything older than the window; the queue’s length is the count.
Let the queue's meaning write the method
| Variable | Always means, when ping returns |
|---|---|
self.queue |
the pings in [t - 3000, t], oldest at the front |
| Code | What happened | What it restores |
|---|---|---|
self.queue = deque([]) |
no pings yet | the window is empty |
self.queue.append(t) |
a new ping at t |
it is the newest, so it goes at the back |
while self.queue[0] < t - 3000: |
the window moved to [t - 3000, t] |
the front may now be too old |
self.queue.popleft() |
the front expired | drop it; the next one may have expired too |
return len(self.queue) |
the front is inside the window | everything behind it is newer, so the whole queue counts |
The while never runs on an empty queue: t was just appended, and t is never older than t - 3000, so the loop stops at t at the latest.
deque comes from collections. LeetCode imports it for you; running this file elsewhere needs from collections import deque at the top.
The method carries over: state what the queue holds, then a new event goes in the back, and the front is trimmed until the meaning holds again.
Alternatives compared
| Approach | Time per ping | Space | How it works |
|---|---|---|---|
| Keep every ping, count each time | O(n) | O(n) | Store all pings and count those in [t - 3000, t] on every call. |
| Keep every ping, binary search | O(log n) | O(n) | Pings arrive sorted, so bisect finds where the window starts; the answer is the distance to the end. |
| Queue (chosen) | O(1) amortized | O(3001) | Add each ping at the back and drop expired ones from the front. |
| Ring buffer | O(1) amortized | O(3001) | The same queue stored in a fixed list of 3001 slots, with front and back indices that wrap around. |
The queue forgets pings that can never count again, so its memory stays bounded by the window, while the first two keep all n pings. The ring buffer saves the queue’s allocations but needs the window size fixed in advance.
solution.py
class RecentCounter:
def __init__(self):
self.queue = deque([])
def ping(self, t: int) -> int:
self.queue.append(t)
while self.queue[0] < t - 3000:
self.queue.popleft()
return len(self.queue)
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)Notes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.