LeetCode Challenge #933. Number of Recent Calls

Question 27 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #933. Number of Recent Calls

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.

Video Solution

C++ Solution

				
					class RecentCounter {
public:
    RecentCounter() {
    }
    queue<int> q;
    int ping(int t) {
        if(q.empty())q.push(t);
        else{
            while(!q.empty() and (q.front()< (t-3000)))q.pop();
            q.push(t);
        }
        return q.size();
    }
};

Code Explanation

The purpose of this function is to maintain a queue of timestamps representing recent requests. The sliding window concept is used here for the same, and the ‘ping’ method updates the queue and returns the number of requests made in the last 3000 milliseconds(3 seconds).

Let’s see the step-by-step approach towards the problem :

We will initialise a class queue name ‘q’ as a member variable, for storing the integers up to 3000 milliseconds.
If any time stamp is encountered it takes a timestamp ‘t’ as a parameter, representing the time of a new request.
If the queue is empty, then we’ll push the current timestamp onto the queue.

if the timestamp is not empty, it removes timestamps from the front of the queue that are older than 3000 milliseconds then, it pushes the current timestamp onto the queue.

The number of requests that have happened in the inclusive range, will be the number of elements present in the queue so that means, we have to return the size of the queue.
return ( q.size() );

Question 27 of 75 - LeetCode Weekly Challenge