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
- Keep a deque of hit timestamps.
hitsimply appends. getHitspops from the front while the oldest hit is outside the 300-second window.- The window is
(timestamp - 300, timestamp], so a hit exactly 300 seconds old is expired: the eviction condition is<= timestamp - 300. - 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.