Approach 1: Queue
We only care about the most recent calls in the last 3000 ms, so let's use a data structure that keeps only those.
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.
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.