LeetCode 933 - Number of Recent Calls

Difficulty: 🟢 Easy
Topics: Design, Queue, Data Stream

Solution

Problem Understanding

The problem asks us to implement a class RecentCounter that tracks the number of requests (or pings) made in the last 3000 milliseconds. Every time the ping(t) method is called with a time t, we are asked to return how many requests occurred within the time interval [t - 3000, t]. The class starts with zero requests, and each call to ping uses a strictly increasing time value t.

The input t represents time in milliseconds, and the output is simply the count of recent requests within the 3000 millisecond window. The key constraints are that t is strictly increasing and there can be at most 10,000 calls. This guarantees we never have to handle out-of-order timestamps and that the data structure we use will hold at most 10,000 items, which is moderate in size.

Important edge cases include the first request, requests that are exactly 3000 milliseconds apart, and bursts of requests that all fall within the 3000 millisecond window. The guarantee of strictly increasing t simplifies management because we only ever need to remove older requests from the front of the queue, never search or reorder.

Approaches

A brute-force approach would store all requests in a list and, for each ping(t), iterate through the list to count how many timestamps are in the range [t - 3000, t]. This is correct because it literally checks the condition for every request, but it is inefficient because each call takes linear time relative to the number of stored requests.

The optimal approach uses a queue to maintain only the requests within the last 3000 milliseconds. Each time we call ping(t), we append the new timestamp and remove any timestamps from the front that are older than t - 3000. This works because the input guarantees strictly increasing times, so all outdated requests will always be at the front. The queue ensures efficient O(1) insertion and removal from the ends.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per ping	O(n)	Iterates over all previous requests to count recent ones
Optimal	O(1) amortized per ping	O(n)	Uses a queue to only store relevant requests, removing old ones efficiently

Algorithm Walkthrough

Initialize an empty queue when the RecentCounter object is created. This queue will hold all timestamps of recent requests within the 3000 millisecond window.
When ping(t) is called, append t to the queue. This represents the new incoming request.
Remove timestamps from the front of the queue while the timestamp at the front is less than t - 3000. These requests are outside the 3000 millisecond window and should no longer be counted.
After removing old requests, the length of the queue represents the number of requests in the last 3000 milliseconds. Return this length.

Why it works: The queue invariant ensures that it always contains only timestamps within the valid window [t - 3000, t]. Because t values are strictly increasing, once a timestamp is removed, it will never be relevant again. This guarantees correctness and efficiency.

Python Solution

from collections import deque

class RecentCounter:

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

    def ping(self, t: int) -> int:
        self.queue.append(t)
        while self.queue and self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

In this Python implementation, we use deque from the collections module because it allows O(1) insertion at the back and O(1) removal from the front. Each call to ping appends the new request, then removes outdated requests until only the relevant timestamps remain. The length of the deque is then returned, which directly represents the number of recent requests.

Go Solution

type RecentCounter struct {
	queue []int
}

func Constructor() RecentCounter {
	return RecentCounter{queue: []int{}}
}

func (this *RecentCounter) Ping(t int) int {
	this.queue = append(this.queue, t)
	for len(this.queue) > 0 && this.queue[0] < t-3000 {
		this.queue = this.queue[1:]
	}
	return len(this.queue)
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ping(t);
 */

In Go, we use a slice to implement the queue. We append new timestamps and remove old ones by slicing off the front of the slice. This approach is idiomatic for Go, although slicing creates a new underlying array when the old front is removed, which is still efficient for the problem size.

Worked Examples

For the input sequence [1, 100, 3001, 3002]:

Call	Queue state after insertion	Queue state after removing old	Returned value
ping(1)	[1]	[1]	1
ping(100)	[1, 100]	[1, 100]	2
ping(3001)	[1, 100, 3001]	[1, 100, 3001]	3
ping(3002)	[1, 100, 3001, 3002]	[100, 3001, 3002]	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) amortized per ping	Each request is added once and removed once from the queue, so the total work across all pings is linear
Space	O(n)	The queue stores at most all requests in the last 3000 milliseconds, bounded by number of pings

The amortized time is O(1) because each element is appended and popped exactly once over the lifetime of the queue.

Test Cases

# test cases
obj = RecentCounter()
assert obj.ping(1) == 1  # first ping
assert obj.ping(100) == 2  # still within 3000ms window
assert obj.ping(3001) == 3  # edge case: exactly 3000ms window includes 1
assert obj.ping(3002) == 3  # old 1 is now outside, window includes 100, 3001, 3002

# additional tests
obj = RecentCounter()
assert obj.ping(3000) == 1  # only this ping in window
assert obj.ping(6000) == 1  # previous ping at 3000 is outside window
assert obj.ping(9000) == 1  # previous pings outside window
assert obj.ping(9001) == 2  # window includes 9000 and 9001

Test	Why
ping(1), ping(100), ping(3001), ping(3002)	Tests multiple pings including edge of 3000ms window
ping(3000), ping(6000), ping(9000), ping(9001)	Tests pings with gaps larger than 3000ms to ensure old pings are removed

Edge Cases

One important edge case is the first call to ping. There are no previous requests, so the queue starts empty, and the function must correctly return 1. This is handled naturally by appending to the empty queue.

Another edge case occurs when multiple pings arrive within the same millisecond. The queue will contain multiple identical timestamps, and all should be counted in the returned result. The algorithm handles this without any special logic because all timestamps within [t - 3000, t] are retained.

A third edge case involves a ping exactly 3000 milliseconds after the earliest ping. The inclusive window [t - 3000, t] means the earliest ping should still be counted. Our loop removes only timestamps strictly less than t - 3000, so this edge case is correctly handled.