Number of Recent Calls
The key idea
Timestamps arrive in strictly increasing order, so the only requests that can fall out of the window [t-3000, t] are the OLDEST ones. A FIFO queue lets you append each new ping at the back and pop stale timestamps from the front; the answer is just the queue's size after pruning.
Problem
Design a RecentCounter class that counts the number of recent requests within a fixed time window. The counter starts with zero requests. Each call to ping(t) records a new request at time t (in milliseconds) and returns how many requests have occurred in the inclusive range from t - 3000 to t, counting the new request itself. Every call to ping is guaranteed to use a strictly larger value of t than the previous call.
Constraints
- 1 <= t <= 10^9
- Each test case calls ping with strictly increasing values of t
- At most 10^4 calls will be made to ping
Examples
Input: ["RecentCounter","ping","ping","ping","ping"]
[[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]
Complexity
Time: O(1) Space: O(W)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Stack / Queue problems
- Asteroid CollisionMEDIUM
- Baseball GameEASY
- Basic CalculatorHARD
- Decode StringMEDIUM
- Evaluate Reverse Polish NotationMEDIUM
- Longest Valid ParenthesesHARD
- Min StackMEDIUM
- Remove All Adjacent Duplicates In StringEASY
- Removing Stars From a StringMEDIUM
- Simplify PathMEDIUM
- Valid ParenthesesEASY