Problem 10.3 · Queue, Deque and Monotonic QueueEasy

Number of Recent Calls

PatternCombine Structures to Design Sliding Window: Variable Size

What it teaches: A queue as a sliding time window: add new events at the back, expire old ones from the front.

Practise it on judges as “Number of Recent Calls”.

The problem

Implement RecentCounter with ping(t): record a request at time t (milliseconds, strictly increasing) and return how many requests happened in [t − 3000, t].

Example 1

Input: ops = [RecentCounter, ping, ping, ping, ping]
args = [[], [1], [100], [3001], [3002]]
Output: [null, 1, 2, 3, 3]

Constraints

1 ≤ t ≤ 10⁹
Each t is strictly larger than the previous
At most 10⁴ calls

Pattern clues in the wording

→ Count events in the last X time units
→ Times arrive in order

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

RecentCounter.java · starter

import java.util.*;

class RecentCounter {
    public RecentCounter() {}
    public int ping(int t) { return 0; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["RecentCounter","ping","ping","ping","ping"] args = [[],[1],[100],[3001],[3002]]	[null,1,2,3,3]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: queue of timestamps · O(1) amortised per ping

Optimal: queue of timestamps

Time O(1) amortised per ping Space O(window size)

Offer t, then poll from the front while the front is < t − 3000. The queue size is the answer. Each ping is added and removed once.

Approach 1

import java.util.ArrayDeque;
import java.util.Queue;

class RecentCounter {
    private final Queue<Integer> pings = new ArrayDeque<>();

    public RecentCounter() {}

    public int ping(int t) {
        pings.offer(t);
        while (pings.peek() < t - 3000) pings.poll();
        return pings.size();
    }
}

Verdict: This is how simple sliding-window rate limiters work.

Before you submit

Edge cases and common mistakes

Test these inputs

A ping exactly 3000 ms after another (still counted)
Long gaps that empty the window

Mistakes people make

Scanning the whole history on every ping (O(n) per ping).
Using <= when expiring, which drops a ping exactly at t − 3000.

Interview

Follow-up questions

How is this related to rate limiting?

Command Palette

The problem

Approaches

Optimal: queue of timestamps

Edge cases and common mistakes

Follow-up questions