Number of Recent Calls

Problem

API rate limiters track how many requests arrived in the last N milliseconds. Design a RecentCounter class that counts requests in the past 3000ms: ping(t) adds a new request at time t and returns the count of requests in [t - 3000, t]. Time t is strictly increasing.

ping(1)    → 1   # window [0, 1]:    {1}
ping(100)  → 2   # window [0, 100]:  {1, 100}
ping(3001) → 3   # window [1, 3001]: {1, 100, 3001}
ping(3002) → 3   # window [2, 3002]: {100, 3001, 3002}  (1 evicted)

Solution

Approach: Queue as a sliding time window.

The queue holds exactly the timestamps that are currently inside the 3000ms window, oldest at the front. On each ping(t), append t to the back, then evict from the front every timestamp that has fallen outside [t - 3000, t], and return len(queue). The key insight is that t is strictly increasing, so timestamps enter the queue already sorted - the oldest in-window request is always at the front, which is exactly what popleft removes. That means no sorting and no scanning the middle: you only ever peek and pop the front.

The eviction condition is queue[0] < t - 3000. The window is inclusive on both ends, so a timestamp equal to t - 3000 stays. Trace ping(3002) after 1, 100, 3001 are queued: the boundary is 3002 - 3000 = 2, and queue[0] is 1, which is < 2, so 1 is evicted; 100 is not < 2, so the loop stops. The queue is now {100, 3001, 3002} and the answer is 3. Because each timestamp is appended once and popped at most once, the work is amortized across calls rather than repeated per ping.

Edge cases: The queue and ... guard short-circuits so the front peek never hits an empty deque. A fresh counter or a long idle gap is handled naturally - the new ping clears every stale timestamp and returns 1.

Complexity: O(1) amortized time per ping, O(n) total over n pings since each timestamp is enqueued and dequeued once; O(W) space where W is the max requests in any 3000ms window.