Number of Recent Calls — Queue-Based Sliding Window (LeetCode 933)

Number of Recent Calls (LeetCode 933) is an easy problem that perfectly demonstrates when to use a queue. You maintain a sliding window of timestamps and count how many fall within the last 3000 milliseconds.

The Problem

Design a class RecentCounter that counts the number of recent requests within a certain time frame.

• RecentCounter() — initializes the counter with zero requests
• ping(t) — adds a new request at time t (in milliseconds) and returns the number of requests 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.

ping(1)    → 1   (window [−2999, 1], requests: {1})
ping(100)  → 2   (window [−2900, 100], requests: {1, 100})
ping(3001) → 3   (window [1, 3001], requests: {1, 100, 3001})
ping(3002) → 3   (window [2, 3002], requests: {100, 3001, 3002})

Notice that at ping(3002), timestamp 1 falls outside the window and is removed.

Why a Queue?

Two key observations:

1. Timestamps arrive in sorted order — each t is strictly increasing
2. Old timestamps expire from the front — the oldest timestamp expires first

This is exactly FIFO (First In, First Out). A queue lets us:

• Enqueue each new timestamp at the rear
• Dequeue expired timestamps from the front
• Return the queue length as the count

Python Implementation

from collections import deque

class RecentCounter:
    """
    Queue-based sliding window counter.
    Time: O(1) amortized per ping.
    Space: O(W) where W = max requests in a 3000ms window.
    """

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

    def ping(self, t: int) -> int:
        # Add the new request
        self.queue.append(t)

        # Remove requests outside the window
        while self.queue[0] < t - 3000:
            self.queue.popleft()

        return len(self.queue)

That is the entire solution. Let us break down why it works.

Step-by-Step Trace

RecentCounter()
  queue = []

ping(1):
  append 1         queue = [1]
  check: 1 < 1-3000 = -2999? No
  return len = 1

ping(100):
  append 100        queue = [1, 100]
  check: 1 < 100-3000 = -2900? No
  return len = 2

ping(3001):
  append 3001       queue = [1, 100, 3001]
  check: 1 < 3001-3000 = 1? No (1 is not < 1)
  return len = 3

ping(3002):
  append 3002       queue = [1, 100, 3001, 3002]
  check: 1 < 3002-3000 = 2? Yes → popleft
  queue = [100, 3001, 3002]
  check: 100 < 2? No
  return len = 3

Why Not a List?

You might try using a plain list:

# BAD — O(n) per ping due to pop(0)
class RecentCounterBad:
    def __init__(self):
        self.requests = []

    def ping(self, t):
        self.requests.append(t)
        while self.requests[0] < t - 3000:
            self.requests.pop(0)  # O(n) — shifts all elements!
        return len(self.requests)

list.pop(0) is O(n) because it shifts all remaining elements. deque.popleft() is O(1) because it uses a doubly-linked list internally.

Amortized Complexity

Each timestamp is:

• Enqueued once — O(1)
• Dequeued at most once — O(1)

Across n calls to ping, total enqueues = n, total dequeues are at most n. So total work = O(n), meaning amortized O(1) per call.

The while loop may run multiple times in one call, but across all calls, the total number of pops equals the total number of pushes.

Alternative: Binary Search

Since the queue is always sorted, you could use binary search instead of dequeuing:

import bisect

class RecentCounterBS:
    def __init__(self):
        self.requests = []

    def ping(self, t):
        self.requests.append(t)
        # Find first index >= t - 3000
        idx = bisect.bisect_left(self.requests, t - 3000)
        return len(self.requests) - idx

This is O(log n) per ping but uses O(n) total memory (never removes old timestamps). The queue approach is better because it keeps memory bounded.

Edge Cases

1. First call — ping(1) → always returns 1
2. Exactly 3000ms apart — ping(1) then ping(3001) → both are in window [1, 3001], returns 2
3. Rapid pings — many pings within 3000ms → queue grows but is bounded by the rate
4. Large gap — ping(1) then ping(10000) → all old pings removed, returns 1
5. Minimum input — t = 1 (smallest valid timestamp)

Space Complexity

The queue never holds more timestamps than the number of pings within any 3000ms window. In the worst case (continuous pings every millisecond), that is 3001 elements.

Metric	Value
Time per ping	O(1) amortized
Space	O(min(n, W)) where W = 3001

Real-World Applications

This pattern appears in:

• Rate limiters — “allow at most 100 requests per minute”
• Monitoring dashboards — “requests per second” counters
• Network protocols — sliding window flow control
• Analytics — “active users in the last 5 minutes”

When to Use This Pattern

Use a queue-based sliding window when:

• Events arrive in chronological order
• You need to count events within a fixed time window
• Old events expire and should be discarded
• You want amortized O(1) per event

Related Problems

Problem	Difficulty	Key Idea
LeetCode 933 — Number of Recent Calls	Easy	This problem
LeetCode 346 — Moving Average from Data Stream	Easy	Queue with fixed window
LeetCode 239 — Sliding Window Maximum	Hard	Deque for max tracking
LeetCode 362 — Design Hit Counter	Medium	Similar time window counter

Key Takeaway

Number of Recent Calls is the textbook use case for a queue: events arrive in order, old ones expire from the front, new ones enter at the rear. The deque gives O(1) operations on both ends, making the solution clean and efficient.