Number of Recent Calls
Last Updated: April 1, 2026
Understanding the Problem
We need to build a counter that tracks pings over time and tells us how many pings happened in the last 3000 milliseconds. Each time ping(t) is called, we record the new ping at time t, then count how many of our stored pings fall within the window [t - 3000, t].
The crucial detail is that t is strictly increasing. We never get a ping from the past, which means older pings are always at the "front" of our history. Once a ping falls outside the 3000ms window, it stays outside forever since all future pings will have even larger timestamps.
This property is what makes the problem tractable. We are essentially maintaining a sliding time window where old pings expire from one end and new pings arrive at the other. The question is: what is the cleanest way to manage this window?
Key Constraints:
1 <= t <= 10^9→ Timestamps can be very large, so we cannot allocate an array indexed by timestamp. We need to store only the pings we have seen.- Strictly increasing values of
t→ This is a major simplification. It means pings arrive in sorted order, so older pings are always at the front. A queue-based approach fits perfectly since we only ever remove from the front and add to the back. - At most
10^4calls toping→ Even a linear scan per call would mean at most 10^8 operations in the worst case. In practice the queue approach is much faster because expired pings are removed early.
Approach 1: Brute Force (Store All Pings)
Intuition
The most straightforward approach is to store every ping in a list and, whenever we need the count, scan through the entire list to count pings within the window [t - 3000, t].
This works because we have all the data we need. The downside is that we scan pings that expired long ago, but with at most 10^4 calls, this is still fast enough.
Algorithm
- Maintain a list of all ping timestamps.
- When
ping(t)is called, appendtto the list. - Iterate through the entire list and count how many timestamps fall within
[t - 3000, t]. - Return the count.
Example Walkthrough
Code
- Time Complexity: O(n) per
pingcall, where n is the total number of pings so far. Each call scans the entire list to count valid pings. - Space Complexity: O(n). We store every ping forever, even after it expires.
The bottleneck is scanning the entire history on every call, including expired pings that will never be valid again. What if we removed expired pings so we only scanned the ones that matter?
Approach 2: Queue (Remove Expired Pings)
Intuition
Since timestamps are strictly increasing, expired pings are always at the front of our collection. Once a ping's timestamp is less than t - 3000, it is gone for good. No future call can bring it back into the window.
This is exactly what a queue is built for. Add new pings to the back, remove expired ones from the front. After cleanup, the queue contains only valid pings, so its size is the answer.
Think of it like a conveyor belt. New pings enter from the right. As time passes, the left end of the belt drops off pings that are too old. At any moment, everything on the belt is recent.
The queue maintains a sorted invariant for free since timestamps arrive in increasing order. Every ping that enters the queue will eventually leave it (when a future ping pushes it outside the 3000ms window). The key property is that each ping is added exactly once and removed at most once across all calls, which gives us excellent amortized performance.
The while loop in each ping call might remove zero, one, or many old pings. But across all n calls to ping, the total number of removals can never exceed n (since each ping is removed at most once). So the total work across all calls is O(n), making each call O(1) amortized.
Algorithm
- Initialize an empty queue.
- When
ping(t)is called, addtto the back of the queue. - Remove all elements from the front of the queue that are less than
t - 3000(they are outside the window). - Return the size of the queue.
Example Walkthrough
Code
- Time Complexity: O(1) amortized per
pingcall. Each ping is enqueued once and dequeued at most once across all calls. Over n total calls, the total work is O(n). - Space Complexity: O(w) where w is the maximum number of pings within any 3000ms window. The queue only holds pings that are currently valid.
The queue approach is already excellent. But if an interviewer asks about guaranteed worst-case bounds per call, we can use binary search on the sorted list for O(log n) per call with no amortization.
Approach 3: Binary Search (Sorted List)
Intuition
Since pings arrive in strictly increasing order, our list of pings is always sorted. Instead of removing expired entries, we can keep all pings and use binary search to find the first ping that is within the window [t - 3000, t]. Everything from that index to the end of the list is valid.
This approach does not remove expired pings, so it uses more memory over time. But it gives us a clean O(log n) per call without amortization, meaning every single call is fast.
Algorithm
- Maintain a sorted list of all ping timestamps.
- When
ping(t)is called, appendtto the list (it is already in sorted position since timestamps are increasing). - Binary search for the smallest index where the timestamp is >=
t - 3000. - Return
list.size() - index(everything from that index onward is in the window).
Example Walkthrough
Code
- Time Complexity: O(log n) per
pingcall. Appending is O(1) and the binary search over n elements takes O(log n). No amortization needed. - Space Complexity: O(n) where n is the total number of pings. We never remove old pings, so the list grows indefinitely.