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.

Example 1:

Input: RecentCounter(); ping(200); ping(600); ping(3200); ping(3500)
Output: [null, 1, 2, 3, 3]
Explanation: at t = 3500 the window [500, 3500] holds the requests at 600, 3200, and 3500; the request at t = 200 has aged out.

Constraints:

• 1 <= t <= 10^8
• Each call to ping uses a strictly larger value of t than the previous call.
• At most 10^3 calls will be made to ping.

Solution Breakdown

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(3500) after 200, 600, 3200 are queued: the boundary is 3500 - 3000 = 500, and queue[0] is 200, which is < 500, so 200 is evicted; 600 is not < 500, so the loop stops. The queue is now {600, 3200, 3500} 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.