Skip to content

933. Number of Recent Calls

On LeetCode ->

Problem

Implement a counter whose ping(t) records a request and returns the number of requests in the inclusive interval \([t - 3000, t]\). Timestamps are strictly increasing integers.

ping(t):       1   100   3001   3002
returns:      1     2      3      3
final state: [100, 3001, 3002]

class RecentCounter:
    def __init__(self):
        pass

    def ping(self, t: int) -> int:
        pass

Key trick

Use a queue: increasing timestamps mean expired requests are always at the front and can be permanently removed.

Trap

  • Remove timestamps strictly less than t - 3000, not equal to it.
  • Use deque.popleft(), not the linear-time list.pop(0).
  • A single call can remove many requests; constant time is amortized.

Why is it interesting?

It turns a streaming sliding-window problem into a queue where each request is added and removed at most once.

Python solution

from collections import deque


class RecentCounter:
    def __init__(self):
        self.requests = deque()

    def ping(self, t: int) -> int:
        self.requests.append(t)

        while self.requests[0] < t - 3000:
            self.requests.popleft()

        return len(self.requests)

Time: \(O(1)\) amortized per call, \(O(n)\) total for \(n\) calls.

Space: \(O(\min(n, 3001))\), since an inclusive 3000-millisecond window contains at most 3001 distinct integer timestamps.

Comment on my solution

Your algorithm and boundary condition are correct, with the same complexity as above.

  • Add from collections import deque if it is not imported elsewhere.
  • self.cnt is redundant: len(self.requests) is constant-time and avoids maintaining duplicate state.
  • The nonempty check is safe but unnecessary because the newly appended timestamp cannot expire.