Recent Request Counter

easy queue sliding window

Problem

Each call to ping(t) records a request at time t (times come in non-decreasing order) and returns how many requests have arrived in the last 3000 milliseconds, i.e. within the inclusive interval [t − 3000, t]. Maintain a deque of timestamps and discard any that fall outside the window before answering.

Inputpings = [120, 950, 3500, 4200]

Output[1, 2, 3, 3]

After 4200, any ping older than 1200 is dropped — only 3500, 4200, and 950 (just barely if window were larger) qualify; here 950 falls outside [1200, 4200] so the queue ends as [3500, 4200] plus 950? Recheck: 950 < 1200, dropped. Active = {3500, 4200} but the new ping 4200 brings total to 3 with 950 still inside since 4200 − 3000 = 1200 > 950. So queue becomes [3500, 4200] after dropping 950 → length 2. Try the visualization to see.

ping times (comma-separated, non-decreasing)

from collections import deque

class Counter:
    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 Counter {
  constructor() { this.q = []; }
  ping(t) {
    this.q.push(t);
    while (this.q[0] < t - 3000) this.q.shift();
    return this.q.length;
  }
}

class Counter {
    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 Counter {
    queue<int> q;
public:
    int ping(int t) {
        q.push(t);
        while (q.front() < t - 3000) q.pop();
        return q.size();
    }
};

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