⌘K

Tutor

Leetcode 362. Design Hit Counter

Asked at:

Uber

Google

Apple

DESCRIPTION

Design a hit counter that records timestamps of incoming hits and efficiently queries the number of hits within the past 5 minutes (300 seconds) using a sliding window. The system must handle high-frequency hit(timestamp) and getHits(timestamp) operations by maintaining only relevant data and discarding expired entries. For example, if hits arrive at timestamps [1, 100, 200, 300, 301] and we query at timestamp = 301, only hits at [1, 100, 200, 300, 301] count (all within 300 seconds).

Input:

hit(1)
hit(2)
hit(3)
getHits(4)
getHits(300)
getHits(301)

Output:

null
null
null
3
3
2

Explanation: At timestamp = 4, all 3 hits are within 300 seconds. At timestamp = 300, hits at [1, 2, 3] are still valid. At timestamp = 301, hit at timestamp = 1 expires (301 - 1 = 300 seconds exactly is the boundary), leaving 2 hits.

Constraints:

Timestamps are in seconds and arrive in non-decreasing order
The sliding window is 300 seconds (5 minutes)
Must support high-frequency operations efficiently
1 <= timestamp <= 2 * 10^9

Understanding the Problem

The core challenge is maintaining a dynamic sliding window that automatically discards expired hits while supporting fast queries. A naive approach storing all timestamps wastes memory and requires scanning the entire history on each query. The key insight is that we only need hits from the past 300 seconds, so we can use a queue or circular buffer to maintain a rolling window. When querying, we remove expired entries from the front and count remaining elements.

Building Intuition

A naive approach stores all timestamps in a list and scans from the beginning on each query to count valid hits, resulting in O(n) query time where n is total hits ever recorded. A better approach uses a queue (deque) to store timestamps and removes expired entries during queries, keeping only the sliding window in memory. For example, with hits at [1, 100, 200, 300] and query at 301, we pop 1 from the front (expired) and count the remaining 3 elements in O(k) time where k is hits in the window.

Real-world systems like rate limiters, analytics dashboards, and monitoring tools need to track recent events efficiently without unbounded memory growth. A sliding window approach ensures constant memory usage proportional to the window size, not total event count. This pattern is fundamental for building scalable, high-throughput services.

Common Pitfalls

Forgetting boundary conditions: A hit exactly 300 seconds old should be excluded (use > not >= when checking currentTime - timestamp > 300)

Not removing expired hits during hit() calls: Clean up stale data proactively to prevent memory bloat, not just during queries

Using a list instead of deque: Removing from the front of a list is O(n), while deque.popleft() is O(1)

Implementation

Queue-Based Sliding Window

Use a deque to store timestamps in chronological order, leveraging the fact that timestamps arrive in non-decreasing order. On each hit(timestamp), append the timestamp to the deque and remove expired entries from the front. On getHits(timestamp), clean up expired entries and return the deque's length. For example, with hits [1, 100, 200] and query at 301, we remove 1 (since 301 - 1 = 300, which is not within the past 300 seconds) and return 2.

Solution

from collections import deque
class HitCounter:
    def __init__(self):
        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()
        return len(self.hits)

Optimized Circular Buffer Approach

For scenarios with extremely high frequency hits, use a fixed-size circular buffer with bucketing to reduce memory overhead. Divide the 300-second window into buckets (e.g., 300 buckets of 1 second each) and store hit counts per bucket. On query, sum counts from valid buckets and reset expired ones. For example, with 1-second buckets, a hit at timestamp = 150 increments bucket[150 % 300], and querying at 450 sums buckets [150-449] after clearing buckets [0-149]. This approach uses O(300) space regardless of hit count.

Solution

class HitCounterCircular:
    def __init__(self):
        self.buckets = [0] * 300
        self.times = [0] * 300
    
    def hit(self, timestamp: int) -> None:
        idx = timestamp % 300
        if self.times[idx] != timestamp:
            self.buckets[idx] = 0
            self.times[idx] = timestamp
        self.buckets[idx] += 1
    
    def getHits(self, timestamp: int) -> int:
        total = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                total += self.buckets[i]
        return total

Complete Integration

Combine both approaches into a unified HitCounter class that selects the appropriate strategy based on use case. The queue-based approach (Section 1) is ideal for moderate traffic with precise timestamp tracking, while the circular buffer approach (Section 2) excels under extreme load where approximate counts suffice. Provide a factory method or configuration flag to switch between implementations. For example, instantiate HitCounter(strategy='queue') for exact counting or HitCounter(strategy='bucket', bucket_size=1) for high-throughput scenarios.

Solution

class HitCounter:
    def __init__(self, strategy='queue', bucket_size=1):
        self.strategy = strategy
        if strategy == 'queue':
            self.impl = HitCounterQueue()
        elif strategy == 'bucket':
            self.impl = HitCounterCircular()
        else:
            raise ValueError(f"Unknown strategy: {strategy}")
    
    def hit(self, timestamp: int) -> None:
        self.impl.hit(timestamp)
    
    def getHits(self, timestamp: int) -> int:
        return self.impl.getHits(timestamp)
class HitCounterQueue:
    def __init__(self):
        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()
        return len(self.hits)

What We've Learned

Pattern: Use a deque for sliding windows with chronological data to achieve `O(1)` removal from both ends
Optimization: Bucketing trades precision for memory efficiency in high-frequency scenarios, reducing space from `O(n)` to `O(window_size)`
Use Case: Essential for rate limiting, real-time analytics, and monitoring systems that track recent events without unbounded growth

Problems to Practice

Overview

Lesson

Sliding Window

The Hit Counter problem uses a sliding window approach to maintain hits within a 300-second time window. This lesson teaches the fundamental sliding window pattern that directly applies to maintaining and querying time-based windows of data.

Learn

Longest Substring Without Repeating Characters

medium

Sliding Window

This problem practices maintaining a dynamic sliding window while tracking elements and removing expired ones, similar to how the Hit Counter discards hits outside the 5-minute window. Both require efficient addition and removal of elements from the window.

Practice

Daily Temperatures

medium

Stack

While using a different data structure, this problem shares the concept of efficiently processing time-series data and maintaining relevant historical information. The monotonic stack pattern can be an alternative approach for certain time-window problems requiring efficient lookups.

Practice

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid February, 2026

Uber

Staff

Mid December, 2025

Apple

Senior

Late November, 2025

Apple

Senior

Get Premium to View All 7 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 362. Design Hit Counter

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

Queue-Based Sliding Window

Optimized Circular Buffer Approach

Complete Integration

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact