Number of Recent Calls
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].
One detail drives everything: t is strictly increasing. We never get a ping from the past, so older pings are always at the front of our history. Once a ping falls outside the 3000ms window, it stays outside forever, because every future ping has an even larger timestamp and the window's lower bound t - 3000 only moves forward.
This property makes the problem tractable. We are maintaining a sliding time window where old pings expire from one end and new pings arrive at the other. The remaining question is how to manage that window efficiently.
Key Constraints:
1 <= t <= 10^9→ Timestamps can be large, so we cannot allocate an array indexed by timestamp. We store only the pings we have seen.- Strictly increasing values of
t→ Pings arrive in sorted order, so older pings are always at the front. This lets us remove only from the front and add to the back, which is what a queue supports. - At most
10^4calls toping→ A linear scan per call is at most about 10^8 operations across all calls, which is acceptable but leaves room to do better by discarding expired pings.
Approach 1: Brute Force (Store All Pings)
Intuition
Store every ping in a list. Whenever we need the count, scan the entire list and count the pings that fall within the window [t - 3000, t].
This works because all the data we need is in the list. The cost is that we keep rescanning pings that expired long ago, but with at most 10^4 calls it stays within the time budget.
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 can never be valid again. The next approach discards those expired pings as soon as they fall out of the window, so each scan touches only pings that still count.
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 drops below t - 3000, it can never re-enter the window, because the lower bound only increases on later calls.
A queue handles this directly. Add new pings to the back, remove expired ones from the front. After cleanup, the queue holds only valid pings, so its size is the answer.
A single ping call can remove zero, one, or many pings, so its individual cost is not constant. The bound comes from looking at all calls together: each ping is added to the queue exactly once and removed at most once. Over n calls, removals total at most n, so the total work is O(n) and each call costs 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 gives O(1) amortized time, but a single call can still do O(w) work when many pings expire at once. The next approach trades that amortized bound for a guaranteed O(log n) per call by searching the sorted list instead of removing from it.
Approach 3: Binary Search (Sorted List)
Intuition
Since pings arrive in strictly increasing order, the list of pings is always sorted. Instead of removing expired entries, keep all pings and binary search for the first ping within the window [t - 3000, t]. Everything from that index to the end of the list is valid, so the count is size - index.
This approach never removes pings, so memory grows with the number of calls. In exchange, every call costs O(log n) in the worst case, not just on average.
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.