Number of Recent Calls

easy queue sliding window

Problem

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].

Inputpings = [1, 100, 3001, 3002]

Output[1, 2, 3, 3]

At ping(3002) the window is [2, 3002], so the timestamp 1 is dropped while 100, 3001, 3002 remain → 3.

ping times (comma-separated, non-decreasing)

from collections import deque

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

class RecentCounter {
  constructor() { this.q = []; }
  ping(t) {
    this.q.push(t);
    while (this.q[0] < t - 3000) this.q.shift();
    return this.q.length;
  }
}

class RecentCounter {
    private Deque<Integer> q = new ArrayDeque<>();
    public int ping(int t) {
        q.offer(t);
        while (q.peek() < t - 3000) q.poll();
        return q.size();
    }
}

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

Explanation

We want to count how many requests landed in the last 3000 milliseconds. Since calls arrive in non-decreasing time order, a queue is the perfect tool: new times go in the back, and old times leave from the front.

On ping(t) we first append t to the queue. Then we look at the front, which holds the oldest timestamp. While that front value is older than t - 3000, it has fallen out of the window, so we pop it.

After cleaning out the stale times, everything left in the queue lies in the inclusive range [t - 3000, t], so the answer is just the queue's current size.

Example: pings 1, 100, 3001, 3002. The first three never expire, giving 1, 2, 3. At ping(3002) the window starts at 2, so timestamp 1 is dropped, leaving 100, 3001, 3002 → 3.

Each timestamp is added once and removed at most once, so the cost per call is amortised O(1).

Time: amortised O(1) per call Space: O(window)