Problem statement

https://leetcode.com/problems/design-hit-counter/

Solution

We can keep our hits in queue, and remove outdated elements when needed.

Complexity

Complexity of hit is $O(1)$, amortized time complexity of getHits is $O(1)$ as well, because each element we put and remove from queue only once. Space complexit is $O(300)$: at any moment there can be no more than $300$ elements in queue.

Code

class HitCounter:
    def __init__(self):
        self.queue = deque()

    def hit(self, timestamp):
        self.queue.append(timestamp)

    def getHits(self, timestamp):
        while self.queue and self.queue[0] <= timestamp - 300:
            self.queue.popleft()
        return len(self.queue)