933. Number of Recent Calls

Description

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.

Intuition

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.

Approach

1. Queue Data Structure: Use a queue to store the timestamps of the requests (ping calls).
2. Add New Ping: When a new ping arrives, add its timestamp to the queue.
3. Remove Outdated Pings: Continuously remove elements from the front of the queue if they are older than 3000 milliseconds relative to the current time t.
4. Return Count: After processing, the size of the queue represents the number of valid recent pings.

This approach ensures that the ping method runs efficiently and maintains only the necessary data in memory.

Complexity

Time Complexity:

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.

Space Complexity:

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.

Code

C++

class RecentCounter {
public:
    std::queue q;

    RecentCounter() {}

    int ping(int t) {
        q.push(t);
        while (q.front() < t - 3000) {
            q.pop();
        }
        return q.size();
    }
};

Python

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)

Java

class RecentCounter {
    private Queue q;

    public RecentCounter() {
        q = new LinkedList<>();
    }

    public int ping(int t) {
        q.add(t);
        while (q.peek() < t - 3000) {
            q.poll();
        }
        return q.size();
    }
}

JavaScript

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;
};