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 time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (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 RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1], range is [-2999,1], return 1 recentCounter.ping(100); // requests = [1, 100], range is [-2900,100], return 2 recentCounter.ping(3001); // requests = [1, 100, 3001], range is [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002], range is [2,3002], return 3
Constraints:
1 <= t <= 109ping with strictly increasing values of t.104 calls will be made to ping.One natural approach to solve this problem is to use a queue data structure. A queue is perfect for this task because it works on a first-in-first-out (FIFO) principle. When a new request arrives, we add it to the queue. We also remove requests from the front of the queue that are older than 3000 milliseconds compared to the current time t. This allows us to keep only the requests within the last 3000 milliseconds in the queue. The number of such requests is simply the size of the queue after cleaning.
This solution uses a simple array to act as a queue with two pointers: front and rear. New requests are added to the rear of the queue. Outdated requests, those older than 3000 milliseconds, are removed by incrementing the front pointer. This ensures the time complexity of each ping operation is amortized O(1).
C++
Java
Python
C#
JavaScript
Time Complexity: Amortized O(1) because each request can only be removed once from the queue.
Space Complexity: O(W), where W is the maximum number of recent requests within 3000 milliseconds.
An alternative approach to using a queue is to use a double-ended queue (deque). While similar to a queue, a deque allows us to add and remove elements from both ends, but in this problem, we'll only need the standard queue operations.
The logic remains the same: insert new request times to the back of the deque and remove outdated ones from the front. This keeps the deque maintaining only the relevant requests within the [t-3000, t] range.
This C++ implementation uses a deque from the standard library to manage timestamps. Similar to a queue, we check and remove outdated times once each new ping is added.
Python
JavaScript
Time Complexity: Amortized O(1) for each ping due to efficient pop and push operations.
Space Complexity: O(W), where W is size of the time window.
| Approach | Complexity |
|---|---|
| Using a Queue | Time Complexity: Amortized O(1) because each request can only be removed once from the queue. |
| Using a Double-ended Queue (Deque) | Time Complexity: Amortized O(1) for each |
LeetCode Number of Recent Calls Solution Explained - Java • Nick White • 13,479 views views
Watch 9 more video solutions →Practice Number of Recent Calls with our built-in code editor and test cases.
Practice on FleetCode