Solution
Approach 1: Queue
Intuition
We only care about the most recent calls in the last 3000 ms, so let's use a data structure that keeps only those.
Algorithm
Keep a queue of the most recent calls in increasing order of t
. When we see a new call with time t
, remove all calls that occurred before t  3000
.
Complexity Analysis

Time Complexity: , where is the number of queries made.

Space Complexity: , where is the size of the window we should scan for recent calls. In this problem, the complexity can be considered .
Analysis written by: @awice.