Number of Recent Calls

Problem

Design a RecentCounter class that counts requests received in the last 3000 milliseconds.

• RecentCounter() — initializes the counter with no requests recorded.
• ping(t: int) -> int — records a new request at time t (in milliseconds) and returns how many requests occurred in the inclusive window [t - 3000, t], counting this one.

Successive calls to ping use strictly increasing values of t — time only moves forward.

Examples

• Calls: ping(1), ping(100), ping(3001), ping(3002) → Returns: 1, 2, 3, 3 At t=3002 the window is [2, 3002], which excludes the ping at t=1 but keeps 100, 3001, 3002.
• Calls: ping(1), ping(3002) → Returns: 1, 1 The window at t=3002 is [2, 3002]; the ping at t=1 has aged out, leaving only the new one.
• Calls: ping(642), ping(1849), ping(4921) → Returns: 1, 2, 1 At t=4921 the window is [1921, 4921]: both 642 and 1849 fall before 1921, so only the new ping counts.

Constraints

• 1 <= t <= 10^9
• Each t is strictly larger than the previous one
• At most 10^4 calls to ping

Total work across all calls should be O(1) amortized per ping (or O(log n) with binary search).

Think about it first

TL;DR

Sliding-window queue (deque) — O(1) amortized per ping, O(W) space for pings inside the window.

Approach 1 — Brute force: keep everything, rescan every time

The naive design stores every ping in a list and, on each ping, counts how many recorded times fall inside the window.

from typing import List


class RecentCounter:
    def __init__(self) -> None:
        self.times: List[int] = []

    def ping(self, t: int) -> int:
        self.times.append(t)
        lo = t - 3000
        return sum(1 for x in self.times if x >= lo)

Complexity: O(n) per ping (n = pings so far), O(n) space — O(n²) total over all calls.

With 10^4 pings that is up to ~10^8 checks in the worst case. It may pass, but every ping re-examines old times that can never fall inside a future window.

Approach 2 — Binary search over the sorted history

Ping times arrive strictly increasing, so self.times is already sorted, and the window’s contents are a suffix of the list. Use binary search to find where t - 3000 would insert; everything from there to the end is in the window. (Binary search repeatedly halves a sorted range to locate a boundary in O(log n).)

import bisect
from typing import List


class RecentCounter:
    def __init__(self) -> None:
        self.times: List[int] = []

    def ping(self, t: int) -> int:
        self.times.append(t)
        i = bisect.bisect_left(self.times, t - 3000)
        return len(self.times) - i

Walkthrough on ping(1), ping(100), ping(3001), ping(3002):

1. ping(1): times = [1]; boundary for −2999 is index 0 → 1 − 0 = 1.
2. ping(100): times = [1, 100]; boundary for −2900 is index 0 → 2 − 0 = 2.
3. ping(3001): times = [1, 100, 3001]; boundary for 1 is index 0 (1 ≥ 1 stays in) → 3 − 0 = 3.
4. ping(3002): times = [1, 100, 3001, 3002]; boundary for 2 is index 1 (the ping at 1 ages out) → 4 − 1 = 3.

Returns 1, 2, 3, 3 — matches the expected output.

Complexity: O(log n) per ping, but space stays O(n) — the dead prefix is never reclaimed.

Approach 3 — Sliding-window queue (deque)

Because times only increase, once a ping falls outside a window it is outside every future window and can be discarded forever. Keep only in-window pings in a FIFO queue: append the new time, evict expired times from the front, and the queue’s length is the answer.

flowchart TD
    A[ping t] --> B[append t to back of queue]
    B --> C{front < t - 3000?}
    C -->|yes| D[popleft expired ping]
    D --> C
    C -->|no| E[return queue length]

from collections import deque


class RecentCounter:
    def __init__(self) -> None:
        self.window: deque[int] = deque()

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

Walkthrough on ping(1), ping(100), ping(3001), ping(3002):

1. ping(1): window = [1]; lo = −2999, nothing evicted → 1.
2. ping(100): window = [1, 100]; lo = −2900, nothing evicted → 2.
3. ping(3001): window = [1, 100, 3001]; lo = 1, front is 1 which is ≥ 1, kept → 3.
4. ping(3002): window = [1, 100, 3001, 3002]; lo = 2, front 1 < 2 → evict it; new front 100 ≥ 2 stays → length 3 → 3.

Complexity: each ping is appended once and popped at most once over the counter’s whole lifetime, so O(1) amortized per ping. Space is O(W) — only the pings inside the current 3000 ms window (at most all 10^4 in pathological inputs, but typically far fewer).

Common pitfalls

• The window is inclusive on both ends: evict while the front is < t - 3000, not <= — a ping at exactly t - 3000 still counts.
• Forgetting to count the current ping (it must be appended before you measure, or add 1 afterwards).
• Using list.pop(0) instead of deque.popleft() — popping the front of a Python list shifts every element and quietly reintroduces O(n) per eviction.
• Reaching for binary search first: it’s a fine answer, but it never frees expired entries, which matters in a long-running counter.

Pattern takeaway

When events arrive in increasing order and queries ask about a trailing window, expired data stays expired forever, so a FIFO queue that evicts from the front holds exactly the live set. Each element pays O(1) amortized for its single entry and single exit. The same monotonic-time-to-sliding-window-deque pattern appears in rate limiters, moving averages, and other sliding-window problems.