Number of Recent Calls
Problem Description
You have a RecentCounter class which counts the number of recent requests within a certain time frame.
Implement the RecentCounter class:
RecentCounter()Initializes the counter with zero recent requests.int ping(int t)Adds a new request at timet, wheretrepresents some time in milliseconds, and returns the number of requests that has happened in the past3000milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range[t - 3000, t].
It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.
Example 1:
Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]
Explanation
Constraints:
- 1 <= t <= 109
- Each test case will call
pingwith strictly increasing values oft. - At most 104 calls will be made to
ping.
Solve it on LeetCode
Approaches
1. Brute Force with List
Intuition:
The problem requires us to count the number of calls within a sliding window of 3000 milliseconds. One straightforward approach is to maintain a list of timestamps and iterate over them to count how many fall within this range each time a new call is added.
Steps:
- Maintain a list to store each call received in increasing order of time.
- On each call to
ping, calculate the time window[t - 3000, t]. - Iterate over the list and count how many timestamps fall within this window.
Code:
- Time Complexity: Every call takes
O(n)wherenis the number of timestamps stored. This is because we may need to iterate over the list to count. - Space Complexity:
O(n)since we need to store all the timestamps.
2. Optimized with Queue
Intuition:
Instead of iterating over all past calls, we can use a queue to efficiently add new timestamps and remove old ones that fall out of the sliding window, maintaining only the relevant timestamps within the queue.
Steps:
- Use a queue to store timestamps.
- On each call to
ping, add the current timestamp to the queue. - Remove timestamps from the front of the queue if they are older than the start of the sliding window
[t - 3000]. - The size of the queue at any time will give the count of timestamps in the required range.
Code:
- Time Complexity: Each
pingoperation isO(1)on average since we are performing operations that affect only the current and the oldest timestamps. - Space Complexity:
O(n)wherenis the number of timestamps in the last 3000 milliseconds.