933. Number of Recent Calls Easy

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

Approach

Input: A series of strictly increasing integers t, representing the time requests arrive (in milliseconds)

Output: For each ping(t), return the number of requests within the [t - 3000, t] time range

This problem belongs to the typical Basic Simulation Queue category.

We use a queue queue to record all request timestamps, and dynamically maintain a sliding time window [t - 3000, t] in real-time:

1. Initialize an empty queue to store all ping times.
2. Every time ping(t) is called, add the current time t to the end of the queue.
3. Then, check whether the element at the beginning of the queue (the earliest request time) is no longer within the [t - 3000, t] range:
   • If it is not, remove it from the front of the queue.
   • Continue removing until the front element is within the valid time range.
4. Finally, the number of remaining elements in the queue is exactly the number of valid requests within the [t - 3000, t] range. Return its length.

Implementation

python

class RecentCounter:

    def __init__(self):
        # Initialize a list to record the timestamps of all pings
        self.records = []

    def ping(self, t: int) -> int:
        # Append the current timestamp t to the records
        self.records.append(t)

        # Remove all timestamps that fall outside the [t - 3000, t] range (i.e. outdated requests)
        while self.records[0] < t - 3000:
            self.records.pop(0)  # Remove the earliest record from the front of the list

        # Return the number of requests within the valid time window
        return len(self.records)

javascript

var RecentCounter = function() {
    this.records = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    this.records.push(t);

    while (this.records[0] < t - 3000) {
        this.records.shift();
    }

    return this.records.length;
};

Complexity Analysis

• Time Complexity: O(1) amortized per ping operation
• Space Complexity: O(W) where W is 3000

Links

933. Number of Recent Calls (English)

933. 最近的请求次数 (Chinese)