Dare2Solve
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.
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.
ping
calls).t
.This approach ensures that the ping
method runs efficiently and maintains only the necessary data in memory.
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.
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.
class RecentCounter {
public:
std::queue<int> q;
RecentCounter() {}
int ping(int t) {
q.push(t);
while (q.front() < t - 3000) {
q.pop();
}
return q.size();
}
};
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)
class RecentCounter {
private Queue<Integer> q;
public RecentCounter() {
q = new LinkedList<>();
}
public int ping(int t) {
q.add(t);
while (q.peek() < t - 3000) {
q.poll();
}
return q.size();
}
}
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;
};