
Description
The RecentCounter
class simulates a counter that only counts the number of recent requests in the last 3000 milliseconds (or 3 seconds). The class provides a method ping(t)
where t
represents the time of a new request. The method returns the number of requests that have been made within the last 3000 milliseconds, including the current one.
Intuition
The core idea is to maintain a record of recent pings and discard any that are older than 3000 milliseconds from the current time t
. This allows for a dynamic sliding window of time, ensuring that only relevant requests are counted.
Approach
- Queue Data Structure: Use a queue to store the timestamps of the requests (
ping
calls). - Add New Ping: When a new ping arrives, add its timestamp to the queue.
- Remove Outdated Pings: Continuously remove elements from the front of the queue if they are older than 3000 milliseconds relative to the current time
t
. - Return Count: After processing, the size of the queue represents the number of valid recent pings.
This approach ensures that the ping
method runs efficiently and maintains only the necessary data in memory.
Complexity
Time Complexity:
The ping
function operates in O(N) in the worst case, where N is the number of pings in the queue. This is because each ping can result in multiple outdated elements being removed from the queue.
Space Complexity:
The space complexity is O(N) as well, where N is the number of recent pings (within the last 3000 milliseconds). This is the maximum number of timestamps stored in the queue at any time.
Code
C++
class RecentCounter {
public:
std::queue q;
RecentCounter() {}
int ping(int t) {
q.push(t);
while (q.front() < t - 3000) {
q.pop();
}
return q.size();
}
};
Python
class 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)
Java
class RecentCounter {
private Queue q;
public RecentCounter() {
q = new LinkedList<>();
}
public int ping(int t) {
q.add(t);
while (q.peek() < t - 3000) {
q.poll();
}
return q.size();
}
}
JavaScript
var RecentCounter = function () {
this.q = [];
};
RecentCounter.prototype.ping = function (t) {
this.q.push(t);
while (this.q[0] < t - 3000) {
this.q.shift();
}
return this.q.length;
};