Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Number of Recent Calls

Try it yourself
EasyProblemExternal link

Description

A server wants to know how busy it has been lately. Build a RecentCounter that counts the requests in the last 3,000 milliseconds:

  • RecentCounter() starts the counter with no requests.
  • ping(int t) records a new request at time t, in milliseconds, and returns how many requests happened in the window [t - 3000, t], both ends included and the new request counted.

Every call to ping uses a strictly larger t than the call before it.

Examples

Example 1

Input:

["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

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

Explanation:

  • RecentCounter(): start with no requests.
  • ping(1): the window is [−2999, 1]; return 1.
  • ping(100): the window is [−2900, 100]; return 2.
  • ping(3001): the window is [1, 3001]; return 3.
  • ping(3002): the window is [2, 3002]; return 3.

At 3001 the window is [1, 3001], so all three pings count. At 3002 it is [2, 3002], and the ping at 1 has left it: 3.

Example 2

Input:

["RecentCounter", "ping", "ping", "ping"]
[[], [1], [3001], [6002]]

Output: [null, 1, 2, 1]

Explanation:

  • RecentCounter(): start with no requests.
  • ping(1): the window is [−2999, 1]; return 1.
  • ping(3001): the window is [1, 3001]; return 2.
  • ping(6002): the window is [3002, 6002]; return 1.

The window includes its left edge: at 3001, the ping at 1 is exactly 3000 ms old and still counts. At 6002 only 3001 and 6002 are in [3002, 6002].

Example 3

Input:

["RecentCounter", "ping"]
[[], [5000]]

Output: [null, 1]

Explanation:

  • RecentCounter(): start with no requests.
  • ping(5000): the window is [2000, 5000]; return 1.

A single ping is always in its own window.

Constraints

  • 1 ≤ t ≤ 10^9
  • Each test case calls ping with strictly increasing values of t
  • At most 10^4 calls will be made to ping

Editorial

Brute Force

Intuition

Keep every request in a list. When a ping arrives at time t, add it, then go through the whole list and count the requests at t - 3000 or later. Nothing is ever later than t, because the times only go up, so that's exactly the window.

Step-by-Step Explanation

Let's trace the pings at 1, 100, 3001 and 3002:

  1. ping(1): the window is [−2999, 1]. The only kept ping is checked, and it's inside: return 1.
  2. ping(100): the window is [−2900, 100]. All 2 kept pings are checked, and 2 are inside: return 2.
  3. ping(3001): the window is [1, 3001]. All 3 kept pings are checked, and 3 are inside: return 3.
  4. ping(3002): the window is [2, 3002]. All 4 kept pings are checked, and 3 are inside: return 3.

Count Every Ping, Every Time — Green pings are inside the window; dim ones are kept but too old.

Algorithm

  1. Keep a list pings, empty at the start.
  2. On ping(t): append t, then count the entries x with x >= t - 3000.
  3. Return the count.

Code

class RecentCounter {
    vector<int> pings;                       // every request so far
public:
    RecentCounter() {}

    int ping(int t) {
        pings.push_back(t);
        int count = 0;
        for (int x : pings)                  // count the ones inside [t - 3000, t]
            if (x >= t - 3000) count++;
        return count;
    }
};

class RecentCounter:
    def __init__(self):
        self.pings = []                      # every request so far

    def ping(self, t: int) -> int:
        self.pings.append(t)
        count = 0
        for x in self.pings:                 # count the ones inside [t - 3000, t]
            if x >= t - 3000:
                count += 1
        return count

class RecentCounter {
    private final List<Integer> pings = new ArrayList<>();   // every request so far

    public RecentCounter() {}

    public int ping(int t) {
        pings.add(t);
        int count = 0;
        for (int x : pings)                                   // count the ones inside [t - 3000, t]
            if (x >= t - 3000) count++;
        return count;
    }
}

var RecentCounter = function() {
    this.pings = [];                         // every request so far
};

RecentCounter.prototype.ping = function(t) {
    this.pings.push(t);
    let count = 0;
    for (const x of this.pings)              // count the ones inside [t - 3000, t]
        if (x >= t - 3000) count++;
    return count;
};

Complexity Analysis

Time Complexity: O(n) per call, O(n²) for n calls

The k-th call walks a list of k pings.

Space Complexity: O(n)

Every ping is kept forever.

Why This Approach Is Not Efficient

With 10^4 pings 1 ms apart, the calls walk lists of 1, 2, 3, … 10^4 pings: about 5 × 10^7 checks in one test, over the time limit in Python. And almost all of that work is wasted: a ping older than t - 3000 can never count again, because every later call has a larger t.

The times arrive in order, so the old pings are always at the front of the list. Drop them from the front as they expire, add each new one at the back, and what's left is exactly the window. That's a queue.

Optimal Approach - A Queue of Recent Pings

Intuition

Keep only the pings that are still inside the window, oldest first, in a queue. A new ping joins the back. Then, while the front is older than t - 3000, it leaves: it's out of this window and of every window after it. Whatever is left is the answer, so return the queue's size.

One call may drop many pings after a long silence, but each ping is added once and dropped at most once.

Step-by-Step Explanation

Let's trace the pings at 1, 100, 3001 and 3002:

  1. ping(1): 1 joins the queue. The front, 1, is at least −2999, so nothing leaves. The queue holds 1: return 1.
  2. ping(100): 100 joins the queue. The front, 1, is at least −2900, so nothing leaves. The queue holds 2: return 2.
  3. ping(3001): 3001 joins the queue. The front, 1, is at least 1, so nothing leaves. The queue holds 3: return 3.
  4. ping(3002): 3002 joins the queue. 1 is older than 2, so it leaves the front. The queue holds 3: return 3.

A Queue of the Last 3,000 ms — The queue holds the pings from head onward; the dim ones have left for good.

Algorithm

  1. Start with an empty queue.
  2. On ping(t): push t at the back.
  3. While the front is less than t - 3000, pop it.
  4. Return the queue's size.

Code

JavaScript has no queue type, and shift() can copy the whole array, so its version keeps an array and a head index instead.

class RecentCounter {
    queue<int> pings;                        // the requests still inside the last 3000 ms, oldest first
public:
    RecentCounter() {}

    int ping(int t) {
        pings.push(t);
        while (pings.front() < t - 3000) pings.pop();   // out of every window from now on
        return pings.size();
    }
};

from collections import deque

class RecentCounter:
    def __init__(self):
        self.pings = deque()                 # the requests still inside the last 3000 ms, oldest first

    def ping(self, t: int) -> int:
        self.pings.append(t)
        while self.pings[0] < t - 3000:      # older than t - 3000: out of every window from now on
            self.pings.popleft()
        return len(self.pings)

class RecentCounter {
    private final Deque<Integer> pings = new ArrayDeque<>();   // inside the last 3000 ms, oldest first

    public RecentCounter() {}

    public int ping(int t) {
        pings.offerLast(t);
        while (pings.peekFirst() < t - 3000) pings.pollFirst();   // out of every window from now on
        return pings.size();
    }
}

var RecentCounter = function() {
    this.pings = [];                         // every request, in time order
    this.head = 0;                           // the oldest one still inside the last 3000 ms
};

RecentCounter.prototype.ping = function(t) {
    this.pings.push(t);
    while (this.pings[this.head] < t - 3000) this.head++;   // out of every window from now on
    return this.pings.length - this.head;
};

Complexity Analysis

Time Complexity: O(1) amortized per call

Each ping is pushed once and popped at most once, so n calls do at most 2n queue operations in all.

Space Complexity: O(1)

The queue never holds more than 3,001 pings, since the times are distinct integers inside a window 3,000 wide.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Dropping the ping on the window's edge. while self.pings[0] <= t - 3000:

On ping(1), ping(3001) it returns [1, 1] for the pings; the answers are [1, 2]. The window is [t - 3000, t], edges included, so a ping at exactly t - 3000 still counts. Drop only the ones strictly older: < t - 3000.

Dropping only one old ping per call. if self.pings[0] < t - 3000:

On ping(1), ping(2), ping(3), ping(5000) it returns [1, 2, 3, 3] for the pings; the answers are [1, 2, 3, 1]. After a long silence, many pings can leave the window at once. An if drops only the oldest of them, and the rest are counted as recent. Keep dropping with a while.

Counting before the new ping is added. count = len(self.pings)

On ping(1), ping(100) it returns [0, 1] for the pings; the answers are [1, 2]. The request at t is inside its own window, so it has to be in the count: add it before counting, or add one.

Where This Pattern Is Taught

This problem practises a queue as a time window. It's taught in Introduction to Queues, next to Moving Average from Data Stream, which keeps its window by size instead of by time.