Number of Recent Calls - Solution & Explanation

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.