Number of Recent Calls
Count the requests made in the last 3000 milliseconds by keeping their times in a queue and dropping the oldest ones as they fall out of the window.
Problem Understanding
Number of Recent Calls (LeetCode 933): implement RecentCounter. ping(t) records a request at time t milliseconds and returns how many requests happened in the inclusive range [t - 3000, t], counting this one. Each call uses a strictly larger t than the call before.
Example: pings at 1, 100, 3001, 3002 return 1, 2, 3, 3. By 3002 the window is [2, 3002], so the ping at 1 no longer counts.
The Intuition: A Window That Only Slides Forward
The window [t - 3000, t] only ever moves right, because t only grows. So the requests inside it are always a run of the most recent ones.
- Append each new ping to the back of a queue.
- Evict from the front every ping older than t - 3000. Once it is out it never comes back.
- Count what is left.
It is a sliding window where time sets the edges instead of an index, close to Introduction to Sliding Window.
Interactive Walkthrough
WINDOW = [t − 3000, t]
EMPTY QUEUE
pings (the outlined run is the queue)
0
1
2
3
Window from
:
Queue
0
Returned
:
Start with an empty queue of ping times
Next
ping(1): append 1. The window is [-2999, 1]
pings
Every ping is drawn on one row. The outlined run is the queue, the newest ping is filled, and a ping evicted from the front shows in red. Try Edge for a ping exactly 3000 ms old, and Burst to see several pops in one call.
Dry Run Table
Pings: 1, 100, 3001, 3002.
| ping(t) | Window | Popped | Queue | Returns |
|---|---|---|---|---|
| 1 | [-2999, 1] | none | [1] | 1 |
| 100 | [-2900, 100] | none | [1, 100] | 2 |
| 3001 | [1, 3001] | none | [1, 100, 3001] | 3 |
| 3002 | [2, 3002] | 1 | [100, 3001, 3002] | 3 |
The Solution Template
A queue of times. The JavaScript and TypeScript versions use an array with a front index, since Array.prototype.shift is O(n); the C version uses a fixed array, as LeetCode makes at most 10,000 calls.
Number of Recent Calls Code
1var RecentCounter = function() {2 this.queue = [];3 this.front = 0;4};56RecentCounter.prototype.ping = function(t) {7 this.queue.push(t);8 while (this.queue[this.front] < t - 3000) {9 this.front++;10 }11 return this.queue.length - this.front;12};
Edge Cases & Common Mistakes
- Exactly 3000 ms old: still inside the window; pop only when front < t - 3000.
- The queue never empties inside the loop: t itself was just appended and is always in the window, so
frontcannot run past it. - Using
shift()in JavaScript: it moves every element, so busy windows become O(n) per call. - Scanning all past pings: counting with a loop over every call is O(n) per ping and needs memory for all of them.
Summary
Keep the ping times in a queue. On each ping, append t, pop from the front while it is older than t - 3000, and return the queue's size. O(1) amortised time, space bounded by the 3000 ms window.
More practice: DSA interview questions with answers · patterns cheat sheet