Number of Recent Calls

In the RecentCounter class, we want to keep track of the requests that happened within a certain time frame, specifically the last 3000 milliseconds. For this, we need a data structure to store the times of the requests. An easy choice would be a list, but considering the constraints, we could face performance issues.

Instead, we use a queue data structure which efficiently supports operations in O(1) time complexity. The queue will store the timestamps of the requests. When a new request comes in, we add the new timestamp to the end of the queue. Then we remove all timestamps at the start of the queue that are older than 3000 milliseconds from the current timestamp.

Let’s implement this in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from collections import deque

class RecentCounter:

    def __init__(self):
        self.queue = deque()

    def ping(self, t: int) -> int:
        # Add new request timestamp to the end of the queue
        self.queue.append(t)

        # Remove requests older than 3000ms
        while self.queue[0] < t - 3000:
            self.queue.popleft()

        return len(self.queue)

Here, deque is a double-ended queue with O(1) time complexity for append and popleft operations. This is better than a list where these operations are O(n).

In ping, we add the new timestamp t to the end of the queue. Then, while the first timestamp in the queue is more than 3000ms before t, we remove that timestamp from the queue. Finally, we return the number of timestamps left in the queue, which is the number of requests that happened in the last 3000ms.