556. Number of Recent Calls
A server wants to know how busy it has been over the last three seconds. Design a class RecentCounter with:
RecentCounter()— creates a counter with no recorded requests;ping(t)— records a new request arriving at timet(in milliseconds) and returns how many requests, including this one, arrived in the window[t − 3000, t](both ends inclusive).
Every call to ping uses a strictly larger t than the one before it.
The judge creates one RecentCounter and calls ping once for each time in the input, in order; your class must produce each return value.
Example 1:
Input: ping(5), ping(2000), ping(3004), ping(3006)
Output: [1, 2, 3, 3]
Explanation: ping(3006) looks at [6, 3006]: the request at 5 has aged out, leaving 2000, 3004, and 3006 — so it returns 3. The three earlier pings still saw everything.
Example 2:
Input: ping(1), ping(3002)
Output: [1, 1]
Explanation: ping(3002) covers [2, 3002]. The request at time 1 misses the window by one millisecond, so only the new request counts.
Constraints:
- 1 ≤ t ≤ 10⁹
- Each ping uses a strictly larger t than the previous call.
- At most 10⁴ calls are made to ping.
Hints:
Times only ever move forward. Once a request falls out of the 3000 ms window, can it ever come back in?
Keep the in-window requests in a queue. On each ping, push t, then pop from the front while the oldest entry is < t − 3000. The answer is simply the queue's size — each request is pushed once and popped at most once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: ping(5), ping(2000), ping(3004), ping(3006)
Expected output: [1, 2, 3, 3]