LeetCode 933: Number of Recent Calls

Problem Restatement

We need to implement a class called RecentCounter.

It supports one main operation:

ping(t)

Each call records a request at time t, measured in milliseconds.

After recording the request, ping(t) must return how many requests happened in the time range:

[t - 3000, t]

The current request is included.

The problem guarantees that every new t is strictly larger than the previous one. The official statement defines RecentCounter(), ping(t), and the inclusive recent window [t - 3000, t].

Input and Output

Class shape:

class RecentCounter:

    def __init__(self):
        ...

    def ping(self, t: int) -> int:
        ...

Examples

Example:

Input:
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

Output:
[null, 1, 2, 3, 3]

Step by step:

ping(1)

Valid range:

[-2999, 1]

Only request 1 is inside.

Return:

1

Next:

ping(100)

Valid range:

[-2900, 100]

Requests 1 and 100 are inside.

Return:

2

Next:

ping(3001)

Valid range:

[1, 3001]

Requests 1, 100, and 3001 are inside.

Return:

3

Next:

ping(3002)

Valid range:

[2, 3002]

Request 1 is now too old.

Requests 100, 3001, and 3002 are inside.

Return:

3

First Thought: Store All Requests and Count Each Time

One simple solution is to store every request time in a list.

For each ping(t), scan the whole list and count how many values are at least t - 3000.

That works, but each call may scan many old requests that can never be useful again.

Because t always increases, once a request is older than t - 3000, it will also be too old for all future calls.

So we should remove old requests instead of keeping them forever.

Key Insight

This is a sliding window over time.

For each new time t, the valid window is:

[t - 3000, t]

Since calls arrive in increasing order, request times are naturally sorted.

The oldest requests are always at the front.

So we can use a queue:

1. Push the new request time to the back.
2. Remove request times from the front while they are too old.
3. The queue length is the answer.

A request is too old when:

queue[0] < t - 3000

The range is inclusive, so a request at exactly t - 3000 must stay.

Algorithm

Initialize an empty queue:

self.q = deque()

For each ping(t):

1. Append t.
2. Compute the oldest valid time:

left = t - 3000

3. While the queue front is smaller than left, remove it.
4. Return the queue length.

Walkthrough

For calls:

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

The answer sequence is:

[1, 2, 3, 3]

Correctness

The queue stores request times that have been recorded and have not yet become too old.

When ping(t) is called, the algorithm first appends t, so the current request is included.

Then it removes every request time smaller than t - 3000. These requests are outside the required range [t - 3000, t], so they must not be counted.

It keeps every request time greater than or equal to t - 3000. Since all request times are at most t at that moment, every remaining request lies inside [t - 3000, t].

Because t values are strictly increasing, the queue is sorted by time. Therefore, all too-old requests appear at the front, and removing from the front removes exactly the expired requests.

After cleanup, the queue contains exactly the recent requests in the required time window. Returning its length gives the correct count.

Complexity

Let m be the number of calls to ping.

Implementation

from collections import deque

class RecentCounter:

    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        self.q.append(t)

        left = t - 3000

        while self.q[0] < left:
            self.q.popleft()

        return len(self.q)

Code Explanation

We keep a queue of active request times:

self.q = deque()

Each new request is appended:

self.q.append(t)

The oldest valid timestamp is:

left = t - 3000

Then we remove expired requests:

while self.q[0] < left:
    self.q.popleft()

We use < left, not <= left, because the range includes t - 3000.

Finally, the number of recent requests is exactly the queue length:

return len(self.q)

Testing

def run_tests():
    rc = RecentCounter()

    assert rc.ping(1) == 1
    assert rc.ping(100) == 2
    assert rc.ping(3001) == 3
    assert rc.ping(3002) == 3

    rc = RecentCounter()
    assert rc.ping(3000) == 1
    assert rc.ping(6000) == 2
    assert rc.ping(6001) == 2

    rc = RecentCounter()
    assert rc.ping(1) == 1
    assert rc.ping(3002) == 1
    assert rc.ping(6003) == 1

    print("all tests passed")

run_tests()