#933 Number of Recent Calls
the problem
In plain words
RecentCounter.ping(t) records a request at time t (ms) and returns how many requests happened in [t − 3000, t]. Each t is strictly larger than the previous one.
in ping(1), ping(100), ping(3001), ping(3002)
out 1, 2, 3, 3
At 3002 the window is [2, 3002], so ping 1 no longer counts.
- 1 ≤ t ≤ 10⁹
- t strictly increases
- At most 10⁴ calls
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (variable size)
Because times only grow, a ping that is too old now is too old forever. So drop it from the front of a queue — the queue is the window.
solutions
From brute force to optimal
Keep every ping and count those ≥ t − 3000 on each call.
- Append t.
- Scan the whole list and count.
Every old ping is re-checked on every call.
All pings are kept forever.
// On LeetCode, name this class RecentCounter.class RecentCounterScan { private final List<Integer> pings = new ArrayList<>(); public int ping(int t) { pings.add(t); int count = 0; for (int p : pings) if (p >= t - 3000) count++; // re-checks every old ping return count; }}The list is sorted for free, so binary-search the first ping ≥ t − 3000.
- Append t.
- Lower-bound search for t − 3000.
- Answer = size − index.
One binary search over the stored pings.
Still keeps every ping.
// On LeetCode, name this class RecentCounter.class RecentCounterBinarySearch { private final List<Integer> pings = new ArrayList<>(); // sorted for free: t strictly increases public int ping(int t) { pings.add(t); int lo = 0, hi = pings.size() - 1; // first index with pings[i] >= t - 3000 while (lo < hi) { int mid = lo + (hi - lo) / 2; if (pings.get(mid) >= t - 3000) hi = mid; else lo = mid + 1; } return pings.size() - lo; }}Offer t; poll from the front while the front is older than t − 3000; return the size.
offer(t).- While
peek() < t − 3000:poll(). - Return
size().
Each ping is offered once and polled at most once.
Only pings inside the 3000 ms window are kept (at most 3001 because times are distinct integers).
class RecentCounter { private final Queue<Integer> window = new ArrayDeque<>(); // pings inside [t - 3000, t] public int ping(int t) { window.offer(t); // newest joins at the rear while (window.peek() < t - 3000) { window.poll(); // too old for this and every later call } return window.size(); }}Dry run
in the room
How to say it in the interview
talk track
- Point out the key guarantee — strictly increasing t — and explain how it makes eviction permanent.
- Mention that the same pattern is a real rate limiter ("at most N requests per second").
traps
- Using
<=instead of<when evicting — t − 3000 itself is still inside the window.
what they ask next
Follow-ups
Times arrive out of order?
The queue trick breaks. Use a sorted structure (TreeMap of time → count) and query a range.
before you submit
Edge cases to test
- The window is inclusive: a ping at exactly t − 3000 still counts.
- A huge jump in t (say 1 → 10⁹) evicts everything except the current ping.
- The very first ping always returns 1.
practise next
Similar problems
- #362Design Hit CounterMediumin QueuesLeetCode Premium
- #239Sliding Window MaximumHardin Queues