Number of Recent Calls — Sliding Window Queue Design

Problem Statement#

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class with a ping(t) method. Each call to ping with an integer t represents a request at time t milliseconds. Return the number of requests that have been made in the inclusive range [t - 3000, t]. It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Constraints:

• 1 <= t <= 10^9
• Each test case will call ping with strictly increasing values of t.
• At most 10^4 calls will be made to ping.

Input:  ["RecentCounter","ping","ping","ping","ping"]
        [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]
Explanation:
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);    // [1], 1 in [1-3000,1]   → 1
recentCounter.ping(100);  // [1,100], 2 in [-2900,100] → 2
recentCounter.ping(3001); // [1,100,3001], 3 in [1,3001] → 3
recentCounter.ping(3002); // [100,3001,3002], 3 in [2,3002] — 1 is now outside → 3

Input:  ["RecentCounter","ping","ping","ping"]
        [[],[1],[2],[6000]]
Output: [null,1,2,1]
Explanation: At t=6000, only [6000] is in [3000,6000]. Both 1 and 2 are expired.

Input:  ["RecentCounter","ping"]
        [[],[5000]]
Output: [null,1]

Why This Problem Matters#

LC 933 is the canonical introduction to the sliding window queue pattern — maintaining a window over a stream of events by evicting expired entries from the front. This is the foundational data structure behind:

• Rate limiters: "Allow at most 100 requests per minute" — same sliding window logic.
• Real-time analytics: "How many events in the last 5 seconds?" — same queue eviction.
• Network monitoring: Counting packets in a sliding time window.
• API throttling: Track requests per user in rolling windows.

Companies that ask this problem: Amazon (rate limiter design), Google (streaming systems), and LinkedIn (feed analytics). The follow-up to this problem is always "design a rate limiter" — knowing the sliding queue pattern is essential.

The Core Insight#

Because ping timestamps are always strictly increasing, the queue is naturally ordered. When a new ping arrives at time t, all timestamps older than t - 3000 can never satisfy any future window (since future t values are even larger). So we evict them from the front.

The deque (double-ended queue) is perfect here:

• Append new timestamps to the back — O(1).
• Evict expired timestamps from the front — O(1) per eviction.
• The length is the count of valid requests — O(1).

The amortized cost per ping is O(1) because each timestamp is added once and removed at most once. In the worst case (a single ping call that expires many old ones), the eviction loop runs many iterations — but amortized across all calls, it is O(1) per ping.

The queue size is bounded by the window size: at most 3001 timestamps can exist in any 3000ms window, making space effectively O(1) for this problem.

Visual Dry Run#

Pings: 1, 100, 3001, 3002

Note: at ping(3002), t - 3000 = 2. The timestamp 1 is less than 2, so it is outside the window and evicted.

Solution (Optimal)#

# Python — sliding window queue using deque, O(1) amortized per ping
from collections import deque
 
class RecentCounter:
    def __init__(self):
        self.q = deque()  # stores timestamps of pings in sliding window
 
    def ping(self, t: int) -> int:
        # Add the new ping timestamp to the back of the queue
        self.q.append(t)
 
        # Evict all timestamps outside the [t-3000, t] window
        # Since timestamps are strictly increasing, stale ones are always at the front
        while self.q[0] < t - 3000:
            self.q.popleft()
 
        # The queue now holds exactly the in-window pings
        return len(self.q)

// JavaScript — sliding window queue, O(1) amortized per ping
class RecentCounter {
    constructor() {
        this.q = [];  // acts as a queue: push to back, shift from front
    }
 
    ping(t) {
        this.q.push(t);
 
        // Evict timestamps outside [t-3000, t]
        while (this.q[0] < t - 3000) {
            this.q.shift();
        }
 
        return this.q.length;
    }
}

Note: For JavaScript in a production setting where the queue can grow large, use a deque implementation (or a circular buffer) to avoid the O(n) cost of shift(). For this problem's constraint of at most 3001 elements in the window, shift() is acceptable.

Complexity:

Common Mistakes#

1. Using while self.q[0] < t - 3000 without checking if the queue is empty. If the queue is somehow empty (it cannot be here since you just appended t), self.q[0] raises an IndexError. In this problem it is safe because you append before evicting, but always be aware of this guard.

2. Off-by-one: using <= t - 3000 instead of < t - 3000. The window is inclusive: [t - 3000, t]. A ping at exactly t - 3000 is valid. Use strict less-than to evict only pings before the window.

3. Using a list with pop(0) in Python instead of deque.popleft(). list.pop(0) is O(n) because it shifts all elements. deque.popleft() is O(1). This makes a difference for large input.

4. Sorting on every ping. Pings are guaranteed strictly increasing — no sorting needed. The queue is already in order. Trust the constraint.

5. Not returning the length after eviction. Some candidates return the length before evicting, counting expired pings.

Interview Tips#

• Connect to real-world systems: "This is the core of a rate limiter. Replace 3000ms with any window size, and you have a general-purpose sliding window counter."
• Explain amortized O(1): "Each timestamp enters the queue once and leaves at most once. Over all pings, the total work is O(total pings), so each ping is amortized O(1)."
• Mention the JavaScript shift() caveat: in production JavaScript, use a proper deque or circular buffer to avoid O(n) front eviction.
• If asked to generalize: "To support variable window sizes per query, you would keep all timestamps and binary-search for the cutoff — O(log n) per ping but more flexible."

Follow-up Questions#

1. Design a rate limiter that allows at most k requests per time window W. Same sliding queue; return False if len(q) > k after adding the new request.
2. What if timestamps can arrive out of order? Use a sorted structure (like a sorted list or binary heap) instead of a queue; eviction is still by time but requires finding the cutoff with binary search.
3. Support multiple window sizes simultaneously. Maintain one queue per window size, or one sorted list and binary-search for each window boundary.
4. What if you need the count in O(1) without iterating? The queue length already gives the count in O(1) — this is the beauty of the sliding window queue.
5. Fixed-size circular buffer implementation. If the maximum number of events in the window is bounded (like 3001 here), use a fixed-size circular buffer for O(1) space and O(1) operations.

Key Takeaways#

• The sliding window queue pattern: append new events to the back, evict expired events from the front, return the queue length as the count.
• Works because events are strictly increasing in time — stale events always accumulate at the front.
• Amortized O(1) per ping: each timestamp is added once and removed at most once over all calls.
• Use deque.popleft() in Python (O(1)) not list.pop(0) (O(n)); in JavaScript, prefer a circular buffer for large windows.
• The off-by-one on the window boundary (< not <=) is critical: the window is inclusive at t - 3000.
• This pattern is the foundation of rate limiters, streaming analytics, and real-time dashboards — understanding it deeply is essential for system design interviews.