933. Number of Recent Calls

[songyy5517]

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

Intuition Basically, given a series of t, the problem is to keep all the previous elements within the range of [t-3000, t]. From the description, we know that t is always greater the preceding one. Therefore, we can use a queue to store these ts, and remove the out-of-range elements from the end of queue.

[songyy5517]

Approach: Queue

1. Define & Initialize a Queue;
2. Remove the out-of-range elements from the end of the queue;
3. Add the new element to the queue;
4. Return the size of the queue;

Complexity Analysis

• Time complexity: $O(1)$ , adding and removing elements from the queue takes $O(1)$ time;
• Space complexity: $O(1)$ , the maximum size of the queue is 3000, which occupies $O(1)$ space.

[songyy5517]

class RecentCounter {
    // Intuition: Queue.    
    Queue<Integer> queue = null;

    public RecentCounter() {
        queue = new LinkedList();
    }

    public int ping(int t) {
        // 1. Remove all the elements out of [t-3000, t]
        while (!queue.isEmpty() && queue.peek() < t - 3000)
            queue.remove();

        // 2. Add the new element to the queue
        queue.add(t);

        return queue.size();
    }
}

[songyy5517]

2024/5/24