Lesson

10.4No of Recent Calls

You have a RecentCounter class which counts the number of recent requests within a 3000-millisecond time frame.

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].

Input:

Output:

Explanation:

Approach

We use a queue (implemented with an array) to store the timestamps of recent requests. When a new request is added:

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 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.

Input:

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.

Operation	Time Complexity	Space Complexity
`ping`	Amortized O(1)	O(n)
Queue storage	N/A	O(n)

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.