Module 09 · Queues, Heaps, and Streaming Frontiers

083. Recent Counter

Foundation · Download this solution · All solutions and shared helpers

Problem

Implement RecentCounter.ping(t) for strictly increasing integer timestamps. Return the number of pings in the inclusive interval [t-3000,t], including the current ping. The class starts empty. Timestamps outside the current interval never need to be counted again.

Examples

Example 1

run_operations(RecentCounter, [("ping",1),("ping",100),("ping",3001),("ping",3002)])
=> [1, 2, 3, 3]

The lower boundary is inclusive.

Example 2

run_operations(RecentCounter, [])
=> []

No pings produce no counts.

Example 3

run_operations(RecentCounter, [("ping",0),("ping",4000)])
=> [1, 1]

The old ping has fully expired.

Reveal the worked solution and reasoning

Why this mechanism works

Increasing timestamps mean expiration happens in FIFO order. Keep only the active interval in a deque. The left endpoint is inclusive, so discard times strictly below t-3000, not times equal to it.

State and boundaries

times contains exactly the unexpired pings in arrival order after repair.

Protocol

Append the current timestamp.
Remove front timestamps smaller than t-3000.
Return the repaired queue length.

Visualization

t=3001 -> interval [1,3001]
pings 1,100,3001 all remain
t=3002 -> interval [2,3002], so 1 expires

Python implementation

from collections import deque
from structures import run_operations

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

    def ping(self, t):
        self.times.append(t)
        while self.times[0] < t - 3000:
            self.times.popleft()
        return len(self.times)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

run_operations(RecentCounter, [("ping",1),("ping",100),("ping",3001),("ping",3002)])

L6 __init__: self.times = deque()
self=RecentCounter{'times':deque([])}

L9 ping: self.times.append(t)
self=RecentCounter{'times':deque([...])}; t=1

L9 ping: self.times.append(t)
self=RecentCounter{'times':deque([..., ...])}; t=100

L9 ping: self.times.append(t)
self=RecentCounter{'times':deque([..., ..., ...])}; t=3001

L9 ping: self.times.append(t)
self=RecentCounter{'times':deque([..., ..., ..., ...])}; t=3002

L11 ping: self.times.popleft()
self=RecentCounter{'times':deque([..., ..., ...])}; t=3002

Result: [1, 2, 3, 3]. The lower boundary is inclusive.

run_operations(RecentCounter, [])

L6 __init__: self.times = deque()
self=RecentCounter{'times':deque([])}

Result: []. No pings produce no counts.

Why the solution is correct

The new ping belongs to its own interval. All expired pings form a prefix because arrivals are ordered, and future timestamps can never make those old pings relevant again. Removing that prefix leaves exactly the requested inclusive interval.

Time and space

O(1) amortized time per ping and O(w) space for the pings retained in the active window.

Common mistakes

Using <= expires the inclusive lower endpoint incorrectly. Out-of-order timestamps would invalidate FIFO expiration.

Reasoning card

State: times contains exactly the unexpired pings in arrival order after repair.

Invariant: Queue contains exactly pings in the active time window.

Decision to rehearse: Expire old timestamps from the front before reporting.

Finish: Return the repaired queue length

Transfer exercise

Support out-of-order timestamps. Identify which assumptions must change before choosing a replacement data structure.