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.