Number of Recent Calls - Solution & Explanation
Problem Statement
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 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 <= 109- Each test case will call
pingwith strictly increasing values oft. - At most
104calls will be made toping.
Approach Overview
Problem Overview: You need to design a class that tracks the number of requests received within the last 3000 milliseconds. Each call to ping(t) represents a request at time t. The function must return how many requests occurred in the time range [t - 3000, t]. Since timestamps arrive in strictly increasing order, the solution can process the stream incrementally.
Approach 1: Brute Force List Scan (O(n) time, O(n) space)
Store every timestamp in an array or list. When ping(t) is called, iterate through the entire list and count timestamps that fall within the range t - 3000 to t. This approach works because timestamps are preserved in order, but every query scans all stored requests. As the number of pings grows, the scan becomes increasingly expensive. This method demonstrates the core idea of filtering by time window but does not scale well for large data streams.
Approach 2: Queue Sliding Window (O(1) amortized time, O(n) space)
A better approach uses a queue to maintain only the requests that fall inside the valid 3000‑millisecond window. Push the new timestamp t into the queue. Then repeatedly remove elements from the front while the oldest timestamp is smaller than t - 3000. Because timestamps arrive in increasing order, once a value becomes invalid it will never be needed again. The remaining queue size directly represents the number of recent calls. Each timestamp is inserted once and removed once, which gives O(1) amortized time per operation.
This pattern is essentially a sliding window over a data stream. The queue always holds the active window of valid timestamps. Operations are simple: enqueue for new calls and dequeue for expired ones.
Approach 3: Double-Ended Queue (Deque) Optimization (O(1) amortized time, O(n) space)
A deque provides the same behavior as a queue but with more flexible operations on both ends. Insert the new timestamp at the back and remove outdated timestamps from the front while they fall outside the [t - 3000, t] interval. Since removal always happens from the front and insertion from the back, the deque behaves like a sliding window buffer. Languages with optimized deque implementations can make this solution slightly faster in practice while keeping the same algorithmic complexity.
This approach is commonly used when implementing streaming systems or rate limiters, where you maintain a moving time window of events.
Recommended for interviews: The queue-based sliding window solution is what interviewers expect. It shows that you recognize the monotonic timestamp property and can maintain a window efficiently using a queue. Mentioning the brute force approach first shows understanding of the problem constraints, but implementing the queue or deque solution demonstrates practical data structure design skills.
Approach 1: Using a Queue
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).
Complexity
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.
Approach 2: Using a Double-ended Queue (Deque)
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.
Code
C++
Python
JavaScript
Complexity
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 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| 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 |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force List Scan | O(n) per ping | O(n) | Conceptual baseline or very small input sizes |
| Queue Sliding Window | O(1) amortized | O(n) | Best general solution for streaming requests |
| Deque Implementation | O(1) amortized | O(n) | Preferred in languages with efficient deque libraries |
Video Solution
LeetCode Number of Recent Calls Solution Explained - Java • Nick White • 15,298 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Recent Calls easy or hard?
How to solve Number of Recent Calls in O(n)?
Number of Recent Calls Python or Java solution?
What is the best approach for Number of Recent Calls?
What data structure is used in Number of Recent Calls?
What is the time complexity of Number of Recent Calls?
Is Number of Recent Calls asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Number of Recent Calls with our built-in code editor and test cases.
Practice on FleetCode