362.Design_Hit_Counter(Medium).md

362. Design Hit Counter (Medium)

Date and Time: May 1, 2025

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

Walk-through:

Since timestamp is monotonically increasing, we don't need minHeap to order. We can just maintain deque[] and a cnt variable.

hit(): save the pair [timestamp, count] into deque[]. Since the timestamp is monotomically increasing, and the number of hits per second could be huge, so everytime before we add [timestamp, 1] into deque[], we first check if the top of deque[] is the same timestamp, if so, we increment the count of current timestamp from deque[]. Otherwise, initialize the count to be 1. Also increment self.cnt by 1 each time.

getHits(): if timestamp < 300, we can return self.cnt right away. If timestamp > 300, we need to remove the outdated timestamp and update self.cnt, so we can check if the top of deque[0][0] <= timestamp - 300. And return self.cnt.

deque:

class HitCounter:
    # Maintain deque[] with [timestamp, cnt] and cnt variable
    # TC: O(n), n is total timestamp, SC: O(n)
    def __init__(self):
        self.deque = collections.deque()    # [[timestamp: cnt]]
        self.cnt = 0
        
    # If deque[0][0] == timestamp, update deque[0]'s cnt by 1 and increment cnt
    def hit(self, timestamp: int) -> None:
        # Check if timestamp is on top of deque
        if self.deque and timestamp == self.deque[-1][0]:
            _, count = self.deque.pop()
        else:
            count = 0
        self.cnt += 1
        # Update self.deque
        self.deque.append([timestamp, count + 1])
        
    # If timestamp > 300, compare the head of deque's timestamp with timestamp, if it is <= timestamp - 300, remove this from deque and decrement cnt with corresponding cnt
    def getHits(self, timestamp: int) -> int:
        if timestamp > 300:
            # Remove outdated timestamp and decrement self.cnt
            while self.deque and self.deque[0][0] <= (timestamp - 300):
                t, count = self.deque.popleft()
                self.cnt -= count
        return self.cnt


# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)

# self.deque = [[2, 1], [3, 1], [300, 1]], self.cnt = 3
# getHits(301)

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Java

class HitCounter {
    /* 
    deque to store [timestamp, cnt], count to maintain
    hit(): check the top of deque, if same timestamp, increment cnt and count
    getHits(): check if timestamp > 300
    */
    Deque<Pair<Integer, Integer>> deque;
    int count;

    public HitCounter() {
        deque = new ArrayDeque<>();
        count = 0;
    }
    
    public void hit(int timestamp) {
        int cnt;
        if (!deque.isEmpty() && deque.peekLast().getKey() == timestamp) {
            Pair<Integer, Integer> last = deque.pollLast();
            cnt = last.getValue() + 1;
        } else {
            cnt = 1;
        }
        deque.offerLast(new Pair<Integer, Integer>(timestamp, cnt));
        count++;
    }
    
    public int getHits(int timestamp) {
        // Remove the left end timestamp
        if (timestamp > 300) {
            while (!deque.isEmpty() && deque.peekFirst().getKey() <= (timestamp - 300)) {
                count -= deque.pollFirst().getValue();
            }
        }
        return count;
    }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */