https://leetcode.com/problems/number-of-recent-calls

What we need to keep in this problem is sliding window of recent calls. So, we need to remove old calls, if they are too old and append new ones. Ideal data structure is queue, and in python we usualy use deque. So, there are 3 simple steps to succes:

  1. Add new call time to the end of our queue.
  2. Remove old times: we pop from the beginning of our queue until time is not older than last - 3000.
  3. Return length of our queue: it will be exaclty what we need.

Complexity: even though for each call of ping function we can potentially call a lot of popleft(), if we run ping n times we will have O(n) complexity: each element go to queue and from queue only once, so we can say amortised time complexity is O(1). Space complexity can be potentially O(3000).

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

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

If you like the solution, you can upvote it on leetcode discussion section: Problem 0933