Number of Recent Calls — InterviewPrepKit

Solving tips

Recognize a trailing-window count over strictly-increasing timestamps: once a ping ages out it can never re-enter a future window, so it can be discarded forever.
Use a FIFO deque: append t, popleft while the front is < t-3000, and return len(window); O(1) amortized per ping (each ping enters and leaves once).
The window is inclusive on both ends, so evict with strict < (a ping exactly at t-3000 still counts).
Pitfall: use deque.popleft() not list.pop(0), which shifts all elements and reintroduces O(n) per eviction; binary search over the kept list also works but never frees expired entries.

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

Hint 1

Store every ping time in a list. What does answering a ping cost if you rescan the whole list each time?

Hint 2

Times are strictly increasing. Once a ping falls out of some window, can any *future* window ever include it again?

Hint 3

Keep a queue. On each ping, append `t`, then pop from the front while the front is older than `t - 3000`. The queue's length is the answer — each ping is pushed once and popped at most once, so the work is O(1) amortized.

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

This is a design problem with no classic “brute force” beyond the naive design: store every ping in a list and, on each ping, count 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’s ~10^8 element checks in the worst case; it may scrape by, but every ping re-examines ancient history that can never be relevant again.

Approach 2 — Binary search over the sorted history

The insight: ping times arrive strictly increasing, so self.times is already sorted — the window’s contents are a suffix of the list. Find where t - 3000 would insert with binary search; everything from there to the end is in the window. (Binary search: repeatedly halve 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):

ping(1): times = [1]; boundary for −2999 is index 0 → 1 − 0 = 1.
ping(100): times = [1, 100]; boundary for −2900 is index 0 → 2 − 0 = 2.
ping(3001): times = [1, 100, 3001]; boundary for 1 is index 0 (1 ≥ 1 stays in) → 3 − 0 = 3.
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)

The insight: because times only increase, once a ping falls outside a window it is outside every future window — it 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.

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):

ping(1): window = [1]; lo = −2999, nothing evicted → 1.
ping(100): window = [1, 100]; lo = −2900, nothing evicted → 2.
ping(3001): window = [1, 100, 3001]; lo = 1, front is 1 which is ≥ 1, kept → 3.
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 is expired forever — so a FIFO queue that evicts from the front maintains exactly the live set, with each element paying O(1) amortized for its one entry and one exit. This “monotonic time ⇒ sliding-window deque” move recurs in rate limiters, moving averages, and every sliding-window problem in this bank.