Here's the solution:
class RecentCounter
queue := empty queue
function ping(t)
enqueue t
// Remove timestamps outside the window
while front of queue < t - 3000
dequeue
return size of queue
Each timestamp is enqueued once and dequeued at most once. If there are calls to ping, total time is . Amortized per call.