You have a RecentCounter class which counts the number of recent requests within a 3000-millisecond time frame.
Implementation Details
RecentCounter(): Initializes the counter with zero recent requests.ping(t): Adds a new request at time t (milliseconds) and returns the number of requests that have happened in the past 3000 milliseconds, i.e., within [t - 3000, t].
Constraints
1 <= t <= 10^9- Calls to
ping are strictly increasing in t.
- At most
10^4 calls will be made to ping.
Example
Input:
Approach
We use a queue (implemented with an array) to store the timestamps of recent requests. When a new request is added:
- Append the timestamp to the queue.
- Remove timestamps from the front of the queue that are older than
t - 3000.
Steps
- Initialize an empty queue to store timestamps.
- For each
ping(t):
- Add the timestamp
t to the queue.
- Remove timestamps from the front of the queue that are less than
t - 3000.
- Return the size of the queue as the count of recent requests.
Time & Space Complexity
- Time Complexity:
- Each call to
ping has a worst-case complexity of O(n), where n is the number of elements in the queue. This occurs if all timestamps in the queue are outside the valid range.
- Amortized complexity is O(1) because each element is added and removed from the queue exactly once.
- Space Complexity: O(n), where
n is the number of timestamps in the queue.
Code Snippet
-
RecentCounter():
- Initialize an empty queue:
queue = [].
-
ping(1):
- Add
1 to the queue: queue = [1].
- Remove elements <
1 - 3000 (none to remove).
- Return
1.
-
ping(100):
- Add
100 to the queue: queue = [1, 100].
- Remove elements <
100 - 3000 (none to remove).
- Return
2.
-
ping(3001):
- Add
3001 to the queue: queue = [1, 100, 3001].
- Remove elements <
3001 - 3000: Remove 1.
- Return
3.
-
ping(3002):
- Add
3002 to the queue: queue = [100, 3001, 3002].
- Remove elements <
3002 - 3000: Remove 100.
- Return
3.
Complexity Analysis
| Operation | Time Complexity | Space Complexity |
|---|
ping | Amortized O(1) | O(n) |
| Queue storage | N/A | O(n) |
Conclusion
- Using a queue ensures efficient management of timestamps for the
ping method.
- The amortized O(1) complexity makes this approach scalable for up to
10^4 calls.
- By removing outdated timestamps, the queue remains optimized for memory and performance.