Number of Recent Calls

Problem Statement

You are tasked with implementing a class named RecentCounter. This class maintains a count of requests within a fixed time frame of the past 3000 milliseconds. Each method in the class works as follows:

• RecentCounter() - Initializes the RecentCounter object with no prior requests.
• int ping(int t) - Adds a new request at time t (in milliseconds) and returns the number of requests that occurred within the window from t - 3000 to t, inclusive. It is guaranteed that each t is strictly greater than the previous t.

Examples

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 = [-2999, 1]     → return 1
recentCounter.ping(100);  // requests = [1,100], range = [-2900, 100]  → return 2
recentCounter.ping(3001); // requests = [1,100,3001], range = [1,3001] → return 3
recentCounter.ping(3002); // requests = [1,100,3001,3002], range = [2,3002]
                          // remove 1 and 100 → requests = [3001, 3002] → return 3

Constraints

• 1 <= t <= 10^9
• Each call to ping has strictly increasing t values.
• At most 10^4 calls will be made to ping.

Approach and Intuition

Given the strictly increasing nature of t, a sliding window technique works optimally:

1. Data Structure Choice: Use a queue to store the timestamps of the most recent requests. This allows for efficient insertion of new times and removal of outdated ones (i.e., those older than t - 3000).

2. Handling ping(t):

   • Append t to the queue.
   • Remove timestamps from the front of the queue as long as they are less than t - 3000.
   • The size of the queue now reflects the number of requests within the valid 3000ms window.

3. Why a Queue? A queue naturally preserves insertion order, and since we only need to discard old timestamps from the front and insert new ones at the back, this structure is perfect. The amortized time complexity per ping call is O(1), making it scalable up to the maximum allowed calls.

This approach is efficient, intuitive, and leverages the monotonicity constraint in the problem to avoid unnecessary computations.

Solutions

class RecentCounter {
    LinkedList<Integer> requestTimes;
    
    public RecentCounter() {
        this.requestTimes = new LinkedList<Integer>();
    }
    
    public int ping(int t) {
        requestTimes.add(t);
    
        while (requestTimes.getFirst() < t - 3000)
            requestTimes.removeFirst();
    
        return requestTimes.size();
    }
}

class RecentCounter:
    
    def __init__(self):
        self.requests = deque()
    
    def ping(self, timestamp: int) -> int:
        self.requests.append(timestamp)
        while self.requests[0] < timestamp - 3000:
            self.requests.popleft()
        return len(self.requests)