How do you solve Number of Recent Calls?

Use a double-ended queue (deque) to store timestamps of requests. On each ping(t), append t to the queue, then remove from the front all timestamps less than t - 3000. The queue length after this process is the count of recent requests. This approach guarantees efficient updates and queries with O(1) amortized time and O(n) space.

What pattern does Number of Recent Calls use?

The Pattern: Queue (Sliding Window) The Heuristic: When counting or tracking elements within a moving fixed-size window over a stream of ordered events, use a queue to efficiently discard outdated elements and maintain only relevant data for constant-time queries.

Number of Recent Calls | Stacks

Q: What is the time complexity of Number of Recent Calls?

O(n). Each request is enqueued exactly once and dequeued at most once, resulting in O(1) amortized time per ping and O(n) total time for n pings.

Problem

Implement a class RecentCounter that counts the number of recent requests within a 3000 milliseconds window, given a stream of ping requests with timestamps.

1 ≤ t ≤ 10⁹
Each call to ping uses strictly increasing values of t
At most 10⁴ calls will be made to ping

Example

Input: ping(1), ping(100), ping(3001), ping(3002)

Output: [1, 2, 3, 3]

At ping(1), only one request exists in [1-3000, 1] = [-2999, 1], so count is 1. At ping(100), requests at times 1 and 100 are in [100-3000, 100] = [-2900, 100], count is 2. At ping(3001), requests at 1, 100, and 3001 are in [1, 3001], count is 3. At ping(3002), requests at 100, 3001, and 3002 are in [2, 3002], count is 3 because 1 is outside the window and removed.

Approach

Straightforward Solution

A naive approach would store all requests and scan through them on each ping to count those within the window, resulting in O(n) time per ping and O(n) space, which is inefficient for large n.

Core Observation

The problem requires counting the number of requests within a sliding time window of fixed size (3000 milliseconds) ending at the current request time t. This is a classic use case for a queue data structure that maintains only relevant elements.

Path to Optimal

Preview

Recognizing that requests arrive in strictly increasing order allows the use of a queue to store only requests within the last 3000 milliseconds. On each ping, enqueue the new request and dequeue all requests older than t - 3000…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a double-ended queue (deque) to store timestamps of requests. On each ping(t), append t to the queue, then remove from the front all timestamps less than t - 3000…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each request is enqueued exactly once and dequeued at most once, resulting in O(1) amortized time per ping and O(n) total time for n pings.

Space

O(n)

In the worst case, all requests fall within the 3000 milliseconds window and are stored in the queue, requiring O(n) space proportional to the number of pings.

Solution

Python

1from collections import deque
2
3class RecentCounter:
4    def __init__(self):
5        self.requests = deque()
6
7    def ping(self, t: int) -> int:
8        self.requests.append(t)
9
10        while self.requests[0] < t - 3000:
11            self.requests.popleft()
12
13        return len(self.requests)

Step-by-Step Solution

1

Maintain a Queue to Store Request Timestamps

5	`self.requests = deque()`

Objective

To keep track of all request timestamps in the order they arrive for efficient window management.

Key Insight

Using a deque allows constant-time insertion at the back and removal from the front, which matches the natural order of incoming requests and the need to discard outdated requests efficiently.

Interview Quick-Check

Core Logic

The deque stores timestamps in ascending order, enabling efficient removal of outdated requests from the front.

Common Pitfalls & Bugs

Using a list instead of a deque would cause inefficient O(n) removals from the front.

2

Add New Request and Remove Outdated Requests

To update the queue by adding the current request and removing all requests outside the 3000 milliseconds window.

3

Return the Count of Recent Requests

To provide the number of requests within the last 3000 milliseconds after updating the queue.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 10 Critical

while self.requests[0] < t - 3000:

Check if the oldest request is outside the 3000 milliseconds window.

Because timestamps are strictly increasing, the oldest request is at the front; if it is less than t - 3000, it must be removed to maintain the sliding window invariant.

Line 11 Critical

self.requests.popleft()

Remove the oldest request from the deque if it is outdated.

Removing outdated requests prevents counting stale requests and keeps the queue size proportional to the number of recent requests, ensuring correctness and efficiency.

Full line-by-line criticality + rationale for all 5 lines available on Pro.

Test Your Understanding

Why does removing requests older than t - 3000 from the front of the queue guarantee the correct count of recent requests?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Number of Recent Calls from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Number of Recent Calls drill

or drill a free problem

1	`from collections import deque`
2
3	`class RecentCounter:`
4	`def __init__(self):`
5	`self.requests = deque()`
6
7	`def ping(self, t: int) -> int:`
8	`self.requests.append(t)`
9
10	`while self.requests[0] < t - 3000:`
11	`self.requests.popleft()`
12
13	`return len(self.requests)`