Number of Recent Calls

Easy

#0887Time: O(N) per `ping` call, where N is the total number of pings made so far. This is because we have to iterate through the entire list of previous requests for every new ping.Space: O(N), where N is the total number of pings. The list stores every timestamp ever received, so its size grows linearly with the number of calls.3 companies

Patterns

Design Data Stream

Algorithms

Token Bucket

Data structures

Queue

Companies

Roblox Databricks Affirm

Prompt

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Constraints:

1 <= t <= 10⁹
Each test case will call ping with strictly increasing values of t.
At most 10⁴ calls will be made to ping.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves storing all the timestamps of the requests in a list. For each new ping, we add the new timestamp to the list and then iterate through the entire list to count how many timestamps fall within the required time window [t - 3000, t].

Algorithm

Initialize an empty list, requests, in the constructor.
In the ping(t) method:
1. Add the new timestamp t to the requests list.
2. Calculate the lower bound of the time window: lowerBound = t - 3000.
3. Initialize a counter count to 0.
4. Iterate through each timestamp in the requests list.
5. If timestamp >= lowerBound, increment count.
6. Return count.

Walkthrough

We use a dynamic array (like ArrayList in Java) to keep a record of all timestamps received so far. When the ping(t) method is called, we first add the new timestamp t to the end of the list. Then, we iterate through every timestamp stored in the list, checking if it is greater than or equal to t - 3000. We count how many such timestamps exist and return the total count.

1import java.util.ArrayList;2import java.util.List;3 4class RecentCounter {5    private List<Integer> requests;6 7    public RecentCounter() {8        this.requests = new ArrayList<>();9    }10 11    public int ping(int t) {12        this.requests.add(t);13        int lowerBound = t - 3000;14        int count = 0;15        // Iterate through all past requests16        for (int timestamp : this.requests) {17            if (timestamp >= lowerBound) {18                count++;19            }20        }21        return count;22    }23}

Complexity

Time

O(N) per `ping` call, where N is the total number of pings made so far. This is because we have to iterate through the entire list of previous requests for every new ping.

Space

O(N), where N is the total number of pings. The list stores every timestamp ever received, so its size grows linearly with the number of calls.

Trade-offs

Pros

Very simple and straightforward to implement.
Easy to understand the logic.

Cons

Inefficient time complexity, as it re-scans old timestamps that are no longer relevant.
Inefficient space complexity, as it never discards old timestamps, leading to ever-increasing memory usage.

This approach uses a queue to store the timestamps of recent requests. Since the timestamps are strictly increasing, we can efficiently remove old, irrelevant timestamps from the front of the queue. The size of the queue then directly gives us the number of recent requests.

Algorithm

Initialize an empty queue, requests, in the constructor.
In the ping(t) method:
1. Add the new timestamp t to the tail of the requests queue.
2. Calculate the lower bound of the time window: lowerBound = t - 3000.
3. While the queue is not empty and the timestamp at the head of the queue (requests.peek()) is less than lowerBound: a. Remove the element from the head of the queue (requests.poll()).
4. Return the current size of the queue.

Walkthrough

A queue (like LinkedList or ArrayDeque in Java) is an ideal data structure for this problem. It naturally handles the sliding window of time. The key insight is that since new timestamps t are always increasing, any timestamp that is too old for the current window [t - 3000, t] will also be too old for all future windows. Therefore, we can permanently discard them.

When the ping(t) method is called:

We add the new timestamp t to the tail of the queue.
We check the timestamp at the head of the queue. While the head element is less than t - 3000, it's outside our current window, so we remove (poll) it from the queue.
After removing all the outdated timestamps, the remaining elements in the queue are precisely those within the [t - 3000, t] range. The size of the queue is our answer.

1import java.util.Queue;2import java.util.LinkedList;3 4class RecentCounter {5    private Queue<Integer> requests;6 7    public RecentCounter() {8        this.requests = new LinkedList<>();9    }10 11    public int ping(int t) {12        // Add the new request timestamp13        this.requests.add(t);14 15        // Remove requests that are older than t - 300016        while (!this.requests.isEmpty() && this.requests.peek() < t - 3000) {17            this.requests.poll();18        }19 20        // The size of the queue is the number of recent requests21        return this.requests.size();22    }23}

Complexity

Time

Amortized O(1) per `ping` call. Each timestamp is added to the queue once (`add`) and removed from the queue at most once (`poll`). Although a single `ping` call might involve multiple `poll` operations, the total work is proportional to the number of pings, making the average time per ping constant.

Space

O(W), where W is the maximum number of requests that can occur within the 3000ms window. The queue only stores timestamps that are within the recent time frame, so the space usage is bounded by the window size (at most 3001), not the total number of calls.

Trade-offs

Pros

Highly efficient time complexity.
Optimal space complexity, as it only stores relevant data.
The logic elegantly models the sliding window nature of the problem.

Cons

Slightly more complex to reason about than the brute-force list approach, particularly regarding the amortized time complexity.

Solutions

Solution

1public class RecentCounter { private Queue < int > q = new Queue < int >(); public RecentCounter () { } public int Ping ( int t ) { q . Enqueue ( t ); while ( q . Peek () < t - 3000 ) { q . Dequeue (); } return q . Count ; } } /** * Your RecentCounter object will be instantiated and called as such: * RecentCounter obj = new RecentCounter(); * int param_1 = obj.Ping(t); */

1class RecentCounter { private Deque < Integer > q = new ArrayDeque <>(); public RecentCounter () { } public int ping ( int t ) { q . offer ( t ); while ( q . peekFirst () < t - 3000 ) { q . pollFirst (); } return q . size (); } } /** * Your RecentCounter object will be instantiated and called as such: * RecentCounter obj = new RecentCounter(); * int param_1 = obj.ping(t); */

1var RecentCounter = function () { this . q = []; }; /** * @param {number} t * @return {number} */ RecentCounter . prototype . ping = function ( t ) { this . q . push ( t ); while ( this . q [ 0 ] < t - 3000 ) { this . q . shift (); } return this . q . length ; }; /** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */

1class RecentCounter { public: deque < int > q ; RecentCounter () { } int ping ( int t ) { q . push_back ( t ); while ( q . front () < t - 3000 ) { q . pop_front (); } return q . size (); } }; /** * Your RecentCounter object will be instantiated and called as such: * RecentCounter* obj = new RecentCounter(); * int param_1 = obj->ping(t); */

1class RecentCounter : def __init__ ( self ): self . q = deque () def ping ( self , t : int ) -> int : self . q . append ( t ) while self . q [ 0 ] < t - 3000 : self . q . popleft () return len ( self . q ) # Your RecentCounter object will be instantiated and called as such: # obj = RecentCounter() # param_1 = obj.ping(t)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem