Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/933.html

Write a class `RecentCounter` to count recent requests.
It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

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

Example 1:

Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]
Note:

Each test case will have at most 10000 calls to ping.
Each test case will call ping with strictly increasing values of t.
Each call to ping will have 1 <= t <= 10^9.

Algorithm

This question lets implement a RecentCounter class with a ping function. Given a time t, let us find how many pings are in the time range [t-3000, t]. The question stipulates that the time given each time will be greater than the last time, and you only care about the number of times within the time window of 3001.

It is a good choice to use the sliding window Sliding Window. Since numbers are continuously added, a queue can be used. Whenever a new time point t is added, the queue is traversed first. If the previous time is not in the current time window, the queue is removed. Then add the current time point t and return the length of the queue, see the code as follows:

Code

C++

class RecentCounter {
public:
    RecentCounter() {}
    
    int ping(int t) {
        while (!q.empty()) {
        	if (q.front() + 3000 >= t) break;
        	q.pop();
        }
        q.push(t);
        return q.size();
    }

private:
	queue<int> q;
};

All Problems

All Solutions