Number of Recent Calls solution and explanation
Google
9 more videos on this problem
LeetCode Number of Recent Calls Solution Explained - JavaNick White · 4:49 · 15K views
Number of Recent Calls | Leet code 933 | Theory explained + Python codeSai Anish Malla · 7:33 · 6K views
LeetCode 933: Number of Recent CallsEngineering Digest · 13:42 · 6K views
Number of Recent Calls - LeetCode 933 #leetcode #leetcode75Deepti Talesra · 9:00 · 5K views
Leetcode - Number of Recent Calls (Python)Timothy H Chang · 3:26 · 4K views
LeetCode 933. Number of Recent Calls 🔥Queue Explained + Python SolutionDKodeTree · 7:30 · 1K views
Daily Leetcode #184: Oct 01, 2020 - 933. Number of Recent CallsProgramming Live with Larry · 4:17 · 676 views
Number of Recent Calls | LeetCode 933 | October LeetCode Challenge | Day 1Learn Code Repeat · 6:56 · 662 views
LeetCode 933 - Number of Recent Calls | LeetCode 75 | Davi Codes - JavaScriptDavinderpal Rehal · 13:49 · 523 views
Leetcode 933. [easy] Number of Recent CallsFrancesco Manicardi · 2:53 · 426 views
The problem
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.
from collections import deque
class RecentCounter:
def __init__(self):
self.requests = deque()
def ping(self, t: int) -> int:
self.requests.append(t)
while self.requests and self.requests[0] < t - 3000:
self.requests.popleft()
return len(self.requests)import java.util.LinkedList;
import java.util.Queue;
class RecentCounter {
Queue<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.offer(t);
while (!queue.isEmpty() && queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
}#include <queue>
using namespace std;
class RecentCounter {
queue<int> q;
public:
RecentCounter() {
}
int ping(int t) {
q.push(t);
while(q.front() < t - 3000) {
q.pop();
}
return q.size();
}
};class RecentCounter {
constructor() {
this.queue = [];
}
ping(t) {
this.queue.push(t);
while (this.queue[0] < t - 3000) {
this.queue.shift();
}
return this.queue.length;
}
}#include <stdio.h>
#include <stdlib.h>
#define MAX_REQUESTS 10000
typedef struct {
int requests[MAX_REQUESTS];
int front;
int rear;
} RecentCounter;
RecentCounter* recentCounterCreate() {
RecentCounter *obj = (RecentCounter *)malloc(sizeof(RecentCounter));
obj->front = 0;
obj->rear = 0;
return obj;
}
int ping(RecentCounter* obj, int t) {
obj->requests[obj->rear++] = t;
while (obj->requests[obj->front] < t - 3000) {
obj->front++;
}
return obj->rear - obj->front;
}
void recentCounterFree(RecentCounter* obj) {
free(obj);
}using System.Collections.Generic;
public class RecentCounter {
private Queue<int> queue;
public RecentCounter() {
queue = new Queue<int>();
}
public int Ping(int t) {
queue.Enqueue(t);
while (queue.Peek() < t - 3000) {
queue.Dequeue();
}
return queue.Count;
}
}This Python solution employs a deque from the collections module to efficiently append and pop request times. The ping method maintains the relevant requests and returns their count.
Time Complexity: Amortized O(1) because operations on a deque allow for efficient pops from both ends.
Space Complexity: O(W), where W is the count of 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.
from collections import deque
class RecentCounter:
def __init__(self):
self.requests = deque()
def ping(self, t: int) -> int:
self.requests.append(t)
while self.requests and self.requests[0] < t - 3000:
self.requests.popleft()
return len(self.requests)#include <deque>
using namespace std;
class RecentCounter {
deque<int> deq;
public:
RecentCounter() {}
int ping(int t) {
deq.push_back(t);
while (!deq.empty() && deq.front() < t - 3000) {
deq.pop_front();
}
return deq.size();
}
};class RecentCounter {
constructor() {
this.deque = [];
}
ping(t) {
this.deque.push(t);
while (this.deque[0] < t - 3000) {
this.deque.shift();
}
return this.deque.length;
}
}This Python solution utilizes deque to store the request timestamps, allowing constant time addition and removal as we maintain the sliding window.
Time Complexity: Amortized O(1).
Space Complexity: O(W), where W is the relevant request count within 3000 milliseconds.
Approach 3: Default Approach
class RecentCounter {
private queue: number[];
constructor() {
this.queue = [];
}
ping(t: number): number {
this.queue.push(t);
while (this.queue[0] < t - 3000) {
this.queue.shift();
}
return this.queue.length;
}
}
/**
* Your RecentCounter object will be instantiated and called as such:
* var obj = new RecentCounter()
* var param_1 = obj.ping(t)
*/type RecentCounter struct {
q []int
}
func Constructor() RecentCounter {
return RecentCounter{[]int{}}
}
func (this *RecentCounter) Ping(t int) int {
this.q = append(this.q, t)
for this.q[0] < t-3000 {
this.q = this.q[1:]
}
return len(this.q)
}
/**
* Your RecentCounter object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Ping(t);
*/use std::collections::VecDeque;
struct RecentCounter {
queue: VecDeque<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl RecentCounter {
fn new() -> Self {
Self {
queue: VecDeque::new(),
}
}
fn ping(&mut self, t: i32) -> i32 {
self.queue.push_back(t);
while let Some(&v) = self.queue.front() {
if v >= t - 3000 {
break;
}
self.queue.pop_front();
}
self.queue.len() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Queue | Time Complexity: Amortized O(1) because operations on a |
| Using a Double-ended Queue (Deque) | Time Complexity: Amortized O(1). |
| Default Approach | – |
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 |
Frequently asked questions
Is Number of Recent Calls easy or hard?
Number of Recent Calls is classified as an Easy problem on LeetCode with a high acceptance rate. The main challenge is recognizing that timestamps are strictly increasing, which allows a queue-based sliding window solution instead of repeatedly scanning all previous requests.
How to solve Number of Recent Calls in O(n)?
Treat the timestamps as a data stream and maintain a sliding window using a queue. Insert the new timestamp t into the queue and repeatedly remove elements from the front while they are smaller than t - 3000. Because timestamps arrive in sorted order, each element is processed at most twice, giving O(1) amortized time and O(n) total storage.
Number of Recent Calls Python or Java solution?
Both Python and Java implementations use the same sliding window idea. Python typically uses collections.deque, while Java uses ArrayDeque or a LinkedList queue. Each ping pushes the new timestamp and pops outdated values until the window only contains timestamps in the last 3000 milliseconds.
What is the best approach for Number of Recent Calls?
The optimal approach uses a queue to maintain a sliding time window of requests. Each new timestamp is added to the queue, and outdated timestamps smaller than t - 3000 are removed from the front. The remaining queue size equals the number of recent calls. This method runs in O(1) amortized time per operation with O(n) space.
What data structure is used in Number of Recent Calls?
The primary data structure is a queue or deque. It stores timestamps representing requests within the last 3000 milliseconds. By removing outdated timestamps from the front and adding new ones to the back, the structure naturally maintains the valid time window.
What is the time complexity of Number of Recent Calls?
The optimal queue or deque solution runs in O(1) amortized time for each ping operation. Every timestamp is inserted once and removed once from the data structure. Space complexity is O(n) because the queue stores all requests within the current 3000 millisecond window.
Is Number of Recent Calls asked at Google, Amazon, or Meta?
Number of Recent Calls is commonly used in interviews that test data stream processing and queue design patterns. Variants of this problem appear in interviews at companies such as Amazon and Google, especially when discussing sliding window systems or rate limiter design.