Design Hit Counter Using Queue

Design a hit counter that records hits and returns the number of hits in the past 5 minutes (300 seconds). Timestamps are in seconds and are monotonically increasing.

Queue Solution

Store timestamps in a queue. To count hits, remove expired timestamps from the front.

from collections import deque

class HitCounter:
    def __init__(self):
        self.queue = deque()
    
    def hit(self, timestamp):
        """Record a hit. Time: O(1)"""
        self.queue.append(timestamp)
    
    def get_hits(self, timestamp):
        """
        Return hits in past 300 seconds.
        Time: O(1) amortized
        """
        while self.queue and self.queue[0] <= timestamp - 300:
            self.queue.popleft()
        return len(self.queue)

Trace

hit(1)       queue: [1]
hit(2)       queue: [1, 2]
hit(3)       queue: [1, 2, 3]
getHits(4)   → 3 (all within 300s)
hit(300)     queue: [1, 2, 3, 300]
getHits(300) → 4
getHits(301) → remove 1 → queue: [2, 3, 300] → 3

Optimized — Fixed-Size Array

For high throughput, use a fixed-size circular buffer:

class HitCounterOptimized:
    def __init__(self):
        self.times = [0] * 300
        self.hits = [0] * 300
    
    def hit(self, timestamp):
        """Time: O(1)"""
        idx = timestamp % 300
        if self.times[idx] != timestamp:
            self.times[idx] = timestamp
            self.hits[idx] = 1
        else:
            self.hits[idx] += 1
    
    def get_hits(self, timestamp):
        """Time: O(300) = O(1)"""
        total = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                total += self.hits[i]
        return total

Comparison

The array approach uses constant space regardless of hit volume — better for high-throughput systems.

Edge Cases

• No hits — getHits returns 0
• Multiple hits same timestamp — queue stores duplicates; array increments counter
• Timestamps exactly 300 apart — hit(1), getHits(301) → 0 (expired)
• Very high throughput — queue grows large; array stays at 300

When to Use This Pattern

• Rate limiting (API request counters)
• Metrics and monitoring dashboards
• Sliding window aggregations
• Session tracking

Related Problems

• Logger Rate Limiter (LeetCode 359)
• Moving Average from Data Stream (LeetCode 346)
• Number of Recent Calls (LeetCode 933)