Number of Recent Calls

Difficulty: Easy | Acceptance: 78.40% | Paid: No Topics: Design, Queue, Data Stream

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

Implement the RecentCounter class:

• RecentCounter() Initializes the counter with zero recent requests.
• int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that have happened 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.

• Examples
• Constraints
• Queue Approach
• Binary Search Approach
• Two Pointers Approach

Examples

Example 1

Input: [“RecentCounter”, “ping”, “ping”, “ping”, “ping”] [[], [1], [100], [3001], [3002]]

Output: [null, 1, 2, 3, 3]

Explanation:

• At t = 1, the number of requests in [1-3000, 1] is 1.
• At t = 100, the number of requests in [100-3000, 100] is 2.
• At t = 3001, the number of requests in [3001-3000, 3001] is 3.
• At t = 3002, the number of requests in [3002-3000, 3002] is 3.

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.

Queue Approach

Intuition Use a queue to maintain timestamps of recent requests, removing outdated entries older than t-3000.

Steps

• Initialize an empty queue
• For each ping, add the timestamp to the queue
• Remove all timestamps older than t-3000 from the front
• Return the queue size

from collections import deque

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

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

Complexity

• Time: O(n) amortized O(1) per ping
• Space: O(n) where n is the number of pings in the 3000ms window
• Notes: Each element is added and removed at most once, making amortized time O(1)

Binary Search Approach

Intuition Store all timestamps in a sorted list and use binary search to find the count of valid timestamps.

Steps

• Initialize an empty list to store all timestamps
• For each ping, append the timestamp (already sorted due to strictly increasing t)
• Use binary search to find the first index where timestamp >= t-3000
• Return the count from that index to the end

import bisect

class RecentCounter:
    def __init__(self):
        self.timestamps = []

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

Complexity

• Time: O(log n) per ping
• Space: O(n) where n is the total number of pings
• Notes: More efficient per query but uses more space as we never remove old timestamps

Two Pointers Approach

Intuition Use an array with two pointers to simulate a queue without the overhead of queue operations.

Steps

• Initialize an array and a left pointer at 0
• For each ping, append the timestamp
• Move the left pointer past any timestamps older than t-3000
• Return the count from left to the end

class RecentCounter:
    def __init__(self):
        self.timestamps = []
        self.left = 0

    def ping(self, t: int) -> int:
        self.timestamps.append(t)
        while self.timestamps[self.left] < t - 3000:
            self.left += 1
        return len(self.timestamps) - self.left

Complexity

• Time: O(n) amortized O(1) per ping
• Space: O(n) where n is the total number of pings
• Notes: Similar to queue approach but with array-based implementation, may have better cache locality