⚡Flashcard Drill➔
NeetCode #157LC-362MediumArrays & Hashing
← Back to All Problems

#157 · #362 · Design Hit Counter(敲击计数器)

📌 Problem Statement & Constraints

Design a hit counter that counts hits in the past 5 minutes (300 seconds). Implement hit(timestamp) and getHits(timestamp). Timestamps are non-decreasing. Constraints: 1 <= timestamp <= 10^9; at most 300 calls to hit.

💡 Core Algorithmic Approaches

  1. Keep a deque of hit timestamps. hit simply appends.
  2. getHits pops from the front while the oldest hit is outside the 300-second window.
  3. The window is (timestamp - 300, timestamp], so a hit exactly 300 seconds old is expired: the eviction condition is <= timestamp - 300.
  4. Each hit is appended once and popped at most once, so the total cost across all calls is O(number of hits).

💻 Benchmark Python3 Implementation

class HitCounter:
    def __init__(self):
        from collections import deque
        self.hits = deque()

    def hit(self, timestamp: int) -> None:
        self.hits.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        while self.hits and self.hits[0] <= timestamp - 300:
            self.hits.popleft()            # outside the 300-second window
        return len(self.hits)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) amortised per call: each timestamp is appended once and evicted at most once.
💾 Space Complexity
O(number of hits within the window).

⚠️ Interview Pitfalls & Follow-ups

  • Using < timestamp - 300: a hit exactly 300 seconds old is outside the window, so the condition must be <=.
  • Storing counts per second in an array of size 300: a valid O(1)-space design (with modular indexing), but the deque is simpler and equally efficient at these limits.
  • Recomputing the count by scanning all stored hits: O(number of hits) per query, which defeats the deque.
  • Assuming timestamps are strictly increasing: they may repeat, and the deque handles that.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems