933 Number of Recent Calls

link: Number of Recent Calls

Thought

Question ask for numbers of calls in 3000. So sliding windows is my choice here – it will move and drop calls earlier than 3000 – which I don’t care, and keep tracing incoming calls.

Code

class RecentCounter:

    def __init__(self):
        self.t = collections.deque()
        self.cnt = 0

    def ping(self, t):
        """
        :type t: int
        :rtype: int
        """
        while self.t and self.t[0] < t - 3000:
            self.t.popleft()
            self.cnt -= 1
        self.t.append(t)
        self.cnt += 1
        return self.cnt

Runtime

Time: O(n)
Space: O(n)