Number of Recent Calls LeetCode 933

LeetCode 933 — Number of Recent Calls — asks you to implement a RecentCounter class with a single method ping(t). Each call to ping(t) records a new request at time t milliseconds and returns the total number of requests that have occurred in the inclusive range [t-3000, t]. The problem guarantees that each call to ping uses a strictly increasing value of t, meaning no two pings share the same timestamp and each ping always comes after all previous ones.

You can think of the problem as a sliding window that always covers the last 3000 milliseconds. The window moves forward with each new ping; old pings outside the left boundary of the window no longer count. The challenge is to implement this efficiently — a naive approach that rescans all stored pings would be O(n) per call and O(n) total for n pings, but the strictly-increasing constraint makes it possible to do much better.

This problem appears frequently in interview contexts as a clean entry point to sliding window and queue algorithm design. It tests whether you recognize that the FIFO structure of a queue maps perfectly to the chronological ordering of timestamps.

The core algorithm maintains a queue of timestamps. On each call to ping(t), first append t to the back of the queue — this records the new request. Then remove all timestamps from the front of the queue that are strictly less than t-3000, since those pings fall outside the current window. After cleanup, the queue contains exactly the timestamps in [t-3000, t], so its size is the answer to return.

The key implementation detail is the while loop at the front of the queue. Because timestamps are strictly increasing, any timestamp that is too old will be at or near the front — never buried in the middle. The loop runs while the front element is less than t-3000, dequeuing one element at a time. Once the front element is within range, all remaining elements are also within range (since they are larger), so the loop stops.

In Python, collections.deque provides O(1) popleft and O(1) append, making both operations constant time. In Java, ArrayDeque or LinkedList provide the same amortized guarantees. The deque is initialized in the constructor, and the queue state persists between ping calls as an instance variable.

A queue (FIFO structure) is the ideal data structure here because it naturally mirrors chronological order. Timestamps are added in increasing order to the back and expire in the same increasing order from the front. The queue enforces the invariant that the oldest timestamp is always at the front — exactly the element you need to check when the window shrinks.

Compare this to a stack (LIFO): the oldest timestamp would be buried at the bottom, and you could never efficiently remove it without O(n) work. Compare to an array: appending is O(1) but removing the front element is O(n) because all elements shift. The deque gives you O(1) at both ends, matching the two operations this problem requires.

No sorting or searching is ever needed. Because timestamps arrive in sorted order and we only remove from the front, the queue is always sorted automatically. The window boundary check (front < t-3000) requires only a single comparison against the front element, not a scan of the whole structure.

Each timestamp added via ping(t) enters the queue exactly once (during the append step) and leaves the queue exactly once (during some future cleanup loop). Across n total pings, the total number of enqueue operations is n and the total number of dequeue operations is at most n. The combined work is 2n operations for n pings, giving an amortized cost of O(1) per ping regardless of how many elements any single ping removes.

This is the same amortized argument used for dynamic array resizing and for the two-stack queue implementation: individual operations may be expensive, but the total cost across all operations is bounded by a constant multiple of n. A ping that removes 100 expired entries is "charged" for those removals against the 100 earlier pings that inserted them — each earlier ping pre-paid for its own removal.

The worst-case single-call complexity is O(n) if all n prior pings expire at once. But average and amortized complexity is O(1). Space complexity is O(w) where w is the maximum number of pings that can fall within any 3000ms window. In the worst case (pings every millisecond), w is 3001, giving O(1) effective space for this problem.

Consider the sequence ping(1), ping(100), ping(3001), ping(3002). At ping(1): append 1; front is 1, check 1 >= 1-3000 = -2999, so no removal; queue = [1]; return 1. At ping(100): append 100; front is 1, check 1 >= 100-3000 = -2900, so no removal; queue = [1, 100]; return 2.

At ping(3001): append 3001; front is 1, check 1 >= 3001-3000 = 1, boundary is 1 exactly; 1 >= 1 is true so 1 stays; queue = [1, 100, 3001]; return 3. At ping(3002): append 3002; front is 1, check 1 >= 3002-3000 = 2; 1 < 2 so remove 1; front is now 100, check 100 >= 2, yes; queue = [100, 3001, 3002]; return 3.

Notice that ping(3001) returns 3 because the window [1, 3001] includes all three timestamps. And ping(3002) also returns 3 because ping(1) at t=1 has now fallen outside the window [2, 3002]. The sliding window correctly updates with each new call without any global rescan.

Python implementation: from collections import deque; class RecentCounter: def __init__(self): self.q = deque(); def ping(self, t: int) -> int: self.q.append(t); while self.q[0] < t - 3000: self.q.popleft(); return len(self.q). The deque is initialized once; each ping appends t and then runs the while loop to expire old entries. popleft() is O(1) for deque vs O(n) for list.pop(0).

Java implementation: class RecentCounter { ArrayDeque<Integer> q = new ArrayDeque<>(); public int ping(int t) { q.offer(t); while (q.peek() < t - 3000) q.poll(); return q.size(); } }. ArrayDeque.offer() adds to the tail and poll() removes from the head, both in O(1) amortized time. peek() reads the head without removing it for the boundary check.

Both implementations follow the same three-line logic: append, cleanup, size. The only language difference is deque API naming. The critical correctness detail is using strict less-than (< t-3000) in the while condition so that entries exactly at t-3000 are correctly included in the count.

Design Hit Counter — LeetCode 362 — is the direct generalization of LeetCode 933. Instead of a fixed 3000ms window, the window is 300 seconds and calls can arrive at any time (not strictly increasing). This forces a more careful design using a circular array or sorted map to handle out-of-order or repeated timestamps that LeetCode 933 avoids by constraint.

Sliding Window Median — LeetCode 480 — extends the sliding window concept to a harder maintenance problem: instead of just counting elements in the window, you must find the median. This requires two heaps (a max-heap for the lower half and a min-heap for the upper half) and a lazy deletion strategy. The window boundary logic is the same; the maintenance of the invariant is far more complex.

Students Unable to Eat Lunch — LeetCode 1700 — is a queue problem that eliminates the simulation entirely through counting. Task Scheduler — LeetCode 621 — converts a scheduling simulation into a frequency formula. Together, LeetCode 933, 1700, and 621 form a trio that covers the full range of queue-based problem solving: pure queue simulation, counting optimization, and formula derivation.