Number of Recent Calls

EasyDesign · Queue🧩 Queue & Monotonic Deque LeetCode #933 ↗Updated Oct 30, 2026

Problem

Implement RecentCounter. Each call ping(t) records a request at time t milliseconds and returns how many recorded requests (including this one) fall in the inclusive window [t - 3000, t]. Every t is strictly larger than the previous one.

Inputping(1) ping(100) ping(3001) ping(3002)Output1, 2, 3, 3

Inputping(5) ping(3006)Output1, 1

1 ≤ t ≤ 10⁹ · t strictly increasing · ≤ 10⁴ calls

Try it yourself

Java

class RecentCounter {
    public RecentCounter() {
        
    }

    public int ping(int t) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Because times only grow, a request that slides out of the window never comes back. Keep the live requests in a FIFO queue and drop from the front — each one is removed at most once.

PatternQueue & Monotonic Deque

Instinct Arrival order matters, or you need the max/min of a moving window - reach for a FIFO queue, or a deque of indices kept in sorted order.

Memory hack Old ones leave by the front door, weak ones get bounced out the back - so whoever stands at the front is always the champion.

Open the Queue & Monotonic Deque guide →

Approaches

Brute ForceStore All, Count by Scanning

Time O(n) per pingSpace O(n)

Append every timestamp to a list and, on each ping, count how many stored times are at least t - 3000. Nothing is ever thrown away.

Java

class RecentCounter {
    private final List<Integer> times = new ArrayList<>();
    public RecentCounter() { }
    public int ping(int t) {
        times.add(t);
        int count = 0;
        for (int time : times) {
            if (time >= t - 3000) count++;
        }
        return count;
    }
}

Trivially correct, but each ping rescans the whole history.

BetterSorted History + Binary Search

Time O(log n) per pingSpace O(n)

The stored times are already sorted because t increases. Binary search for the first time ≥ t - 3000; everything from there to the end is inside the window.

Java

class RecentCounter {
    private final List<Integer> times = new ArrayList<>();
    public RecentCounter() { }
    public int ping(int t) {
        times.add(t);
        int lo = 0, hi = times.size() - 1; // find first index with time >= t - 3000
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (times.get(mid) < t - 3000) lo = mid + 1;
            else hi = mid;
        }
        return times.size() - lo;
    }
}

Fast queries, but memory still grows with every call ever made.

OptimalSliding Window Queue

Time O(1) amortized per pingSpace O(W), W ≤ 3001

Push t to the back, then pop from the front while the oldest time is below t - 3000. The queue then holds exactly the window, so its size is the answer. Each timestamp is pushed and popped once.

Java

class RecentCounter {
    private final Deque<Integer> window = new ArrayDeque<>();
    public RecentCounter() { }
    public int ping(int t) {
        window.offerLast(t);
        while (window.peekFirst() < t - 3000) window.pollFirst(); // expired for good
        return window.size();
    }
}

Amortized O(1) and memory bounded by the window — the expected answer.

Pro tip

Since times are distinct integers, the window never holds more than 3001 entries — mention that bounded-memory guarantee.

At a glance

Level	Approach	Time	Space
Brute Force	Store All, Count by Scanning	`O(n) per ping`	`O(n)`
Better	Sorted History + Binary Search	`O(log n) per ping`	`O(n)`
Optimal	Sliding Window Queue	`O(1) amortized per ping`	`O(W), W ≤ 3001`

Common pitfalls

Using ≤ instead of < when evicting — t - 3000 itself counts.
Checking the window before adding t — the current ping must be counted.
Comparing Integer objects with == instead of unboxing.

Interview tips

Ask whether times are increasing — that is what makes a plain queue enough.
Point out the brute force keeps data it can never use again.
Explain the amortized cost: every element is enqueued and dequeued once.

Pattern

Queue as a sliding time window → counting events in the last T units of a monotonic stream.

My notes saved in this browser