LC933 Number of Recent Calls 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

Sliding window with a queue — count pings in the last 3000 ms as old ones expire from the front.

Implement a class RecentCounter:

- `RecentCounter()` — Initialize a new counter.
- `int ping(int t)` — Add a new request at time t (in milliseconds), then return the number of requests that happened in the past 3000 milliseconds (including the new one). In other words, return the number of requests that have an arrival time 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.

Example 1

Input:: ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]]
Output:: [null, 1, 2, 3, 3]
Explanation:: Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100); // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001); // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002], range is [2,3002], return 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.

Full solution · Try yourself firstพับไว้ด้านใน — คลิกเมื่อพร้อมดู

This maps directly to the Queue pattern: "Keep the most recent events in a sliding window."

1. Mindset Shift

We need to count how many pings landed within the last 3000 ms — like a time window that slides forward. Old pings that fall off the left edge are discarded.

Key insight: store every ping time in a Queue. New pings go to the back. Pings older than t − 3000 are removed from the front. The remaining size is the answer.

Why a Queue? Because t always increases, so the oldest ping is always at the front — we can remove it with O(1) popleft.

2. The Logic — 3 Steps

Start with an empty deque. Each time ping(t) is called:

Enqueue — append(t) to the back.
Drain old — while the front q[0] < t − 3000, popleft().
Count survivors — return len(q) for pings still in [t − 3000, t].

3. LeetCode-Ready Code

Short and straightforward:

Submit this on LeetCodepython

from collections import deque

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

    def ping(self, t: int) -> int:
        self.q.append(t)          # Step 1: enqueue new ping
        while self.q[0] < t - 3000: # Step 2: drain old
            self.q.popleft()
        return len(self.q)        # Step 3: count survivors

4. Dry Run — Step by Step

Call	Window [t−3000, t]	Queue action	q now (front … back)	return
ping(1)	[−2999, 1]	append 1	1	1
ping(100)	[−2900, 100]	append 100	1 → 100	2
ping(3001)	[1, 3001]	append 3001	1 → 100 → 3001	3
ping(3002)	[2, 3002]	append 3002, then popleft 1 (fell off)	100 → 3001 → 3002	3

Queue direction: left = front (oldest ping) · right = back (newest) — popleft while front < t − 3000. Answers: 1, 2, 3, 3 matching expected output.

5. Edge Cases & Pitfalls

The "inclusive boundary" — use < t − 3000, NOT <=:

A ping at exactly t − 3000 is still inside [t − 3000, t].
Using <= would incorrectly remove it.

Never use list.pop(0)

list.pop(0) is O(n) because it shifts all remaining elements. deque.popleft() is O(1) — always use deque in this category.

Note: while self.q[0] is always safe — we just appended t, so the queue has at least one element (t itself), and t can never be < t − 3000, so the loop always terminates before the queue empties.

6. Time & Space Complexity

Time O(1) amortized per ping — each time is appended and popped at most once.
Space O(w) — w is the max number of pings within any 3000 ms window.

💡 Pattern summary

Sliding window with a queue: when a problem asks for "the most recent items within a time/window", append new items to the back and drain old ones from the front. The queue size is the answer.