LeetCode 362 - Design Hit Counter

The problem asks us to design a data structure that tracks how many events, called "hits", occurred during the last 5 minutes. Every hit comes with a timestamp measured in seconds, and timestamps are guaranteed to arrive in chronological order.

leetcodemediumarraybinary-searchdesignqueuedata-stream

LeetCode Problem 362

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Design, Queue, Data Stream

Solution

Problem Understanding

The problem asks us to design a data structure that tracks how many events, called "hits", occurred during the last 5 minutes. Every hit comes with a timestamp measured in seconds, and timestamps are guaranteed to arrive in chronological order.

The class must support three operations:

  • hit(timestamp) records a new hit at the given second.
  • getHits(timestamp) returns how many hits occurred during the inclusive time window [timestamp - 299, timestamp].
  • The constructor initializes the counter.

The important detail is that the system only cares about the last 300 seconds. Any hit older than 300 seconds should no longer contribute to the answer.

For example, if a hit occurs at timestamp 1, it should still count when querying at timestamp 300, because 300 - 1 = 299, which is still inside the 5 minute window. However, at timestamp 301, that same hit becomes too old and must be excluded.

The constraints provide several useful observations:

  • Timestamps are monotonically increasing, meaning time never moves backward.
  • Multiple hits can happen at the same timestamp.
  • The maximum number of calls is only 300, which means even less efficient solutions could pass.
  • However, the follow up explicitly asks about scalability when the hit volume becomes very large, so we should think about a design that remains efficient under heavy load.

A naive implementation can easily make mistakes around boundary conditions. The biggest edge case is deciding whether hits exactly 300 seconds old should still count. The correct interpretation is that timestamps in the range [timestamp - 299, timestamp] are included. Another important case is handling many hits at the same timestamp efficiently. A design that stores every hit individually may become unnecessarily large if millions of hits arrive during the same second.

Approaches

Brute Force Approach

The simplest solution is to store every hit timestamp in a list or queue. Whenever hit(timestamp) is called, we append the timestamp to the structure.

When getHits(timestamp) is called, we iterate through all stored timestamps and count how many fall within the last 300 seconds.

This approach is correct because every recorded hit is checked directly against the valid time window. If the timestamp is recent enough, it contributes to the answer.

However, this solution becomes inefficient as the number of hits grows. Every query requires scanning the entire collection of hits, including very old entries that are no longer relevant. If millions of hits arrive, the query time becomes prohibitively expensive.

Optimal Approach

The key observation is that timestamps arrive in chronological order. Because of this ordering guarantee, old hits naturally accumulate at the front of the data structure.

Instead of scanning everything repeatedly, we can use a queue and remove expired hits as soon as they fall outside the 300 second window.

The algorithm works like this:

  • Store every hit timestamp in a queue.

  • When querying:

  • Remove timestamps from the front while they are older than 300 seconds.

  • The remaining queue size is the answer.

This is efficient because each hit is inserted once and removed once. No timestamp is processed repeatedly.

For the follow up scenario with extremely high hit rates, we can compress multiple hits occurring during the same second by storing (timestamp, count) pairs instead of individual timestamps. This reduces memory usage dramatically.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per query O(n) Scan all hits every time
Optimal O(1) amortized O(n) Queue removes expired hits incrementally

Algorithm Walkthrough

Optimal Queue-Based Algorithm

  1. Initialize an empty queue to store hit timestamps.

The queue preserves chronological order automatically because timestamps are guaranteed to arrive in increasing order. 2. When hit(timestamp) is called, append the timestamp to the queue.

Each occurrence of a hit is stored independently. If three hits occur at the same second, that timestamp is added three times. 3. When getHits(timestamp) is called, remove expired timestamps from the front of the queue.

A timestamp is expired if:

$timestamp - old_timestamp \geq 300$

This means the hit occurred more than 299 seconds ago and no longer belongs in the valid window. 4. Continue removing timestamps until the front of the queue becomes valid again.

Since timestamps are ordered chronologically, once the front is valid, all later timestamps are also valid. 5. Return the size of the queue.

Every remaining timestamp corresponds to a hit inside the last 300 seconds.

Why it works

The queue always maintains an important invariant: every timestamp inside it belongs to the valid 300 second window.

Whenever getHits is called, expired timestamps are removed from the front until the invariant is restored. Since timestamps are inserted in sorted order and never reordered, removing from the front is sufficient. Therefore, the queue size always equals the number of valid hits.

Python Solution

from collections import deque
from typing import Deque

class HitCounter:

    def __init__(self):
        self.queue: Deque[int] = deque()

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

    def getHits(self, timestamp: int) -> int:
        while self.queue and timestamp - self.queue[0] >= 300:
            self.queue.popleft()

        return len(self.queue)

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

The implementation uses Python's deque because it supports efficient insertion at the back and removal from the front.

The constructor initializes an empty queue.

The hit method simply appends the timestamp. Since timestamps are already ordered chronologically, no sorting or binary search is needed.

The getHits method repeatedly removes outdated timestamps from the front. The condition:

timestamp - self.queue[0] >= 300

identifies hits that are older than the valid 300 second window.

After cleanup, every remaining timestamp is valid, so the queue length directly represents the number of recent hits.

Go Solution

type HitCounter struct {
    queue []int
}

func Constructor() HitCounter {
    return HitCounter{
        queue: []int{},
    }
}

func (this *HitCounter) Hit(timestamp int) {
    this.queue = append(this.queue, timestamp)
}

func (this *HitCounter) GetHits(timestamp int) int {
    for len(this.queue) > 0 && timestamp-this.queue[0] >= 300 {
        this.queue = this.queue[1:]
    }

    return len(this.queue)
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Hit(timestamp);
 * param_2 := obj.GetHits(timestamp);
 */

The Go implementation uses a slice as the queue.

Appending new timestamps uses append, while removing expired entries is handled by slicing:

this.queue = this.queue[1:]

Unlike Python's deque, Go slices do not provide true O(1) front removal because the underlying array reference changes. However, given the problem constraints, this implementation is perfectly acceptable.

Go integers safely handle the timestamp range because the maximum timestamp value is only 2 * 10^9, which fits comfortably inside a 64 bit integer and also inside Go's standard int on modern systems.

Worked Examples

Example 1

Input:

["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]

Step-by-step Trace

Operation Queue State Returned Value
HitCounter() [] null
hit(1) [1] null
hit(2) [1, 2] null
hit(3) [1, 2, 3] null
getHits(4) [1, 2, 3] 3
hit(300) [1, 2, 3, 300] null
getHits(300) [1, 2, 3, 300] 4
getHits(301) [2, 3, 300] 3

Detailed Explanation of getHits(301)

Before cleanup:

[1, 2, 3, 300]

Check the oldest timestamp:

301 - 1 = 300

Since this is greater than or equal to 300, timestamp 1 is expired and removed.

Queue becomes:

[2, 3, 300]

Now:

301 - 2 = 299

This timestamp is still valid, so cleanup stops.

The queue contains 3 valid hits.

Complexity Analysis

Measure Complexity Explanation
Time O(1) amortized Each timestamp is inserted once and removed once
Space O(n) Stores all hits within the current 300 second window

Although getHits may remove multiple elements in a single call, each timestamp can only be removed once during the entire lifetime of the program. This gives an amortized constant time complexity.

The space complexity depends on how many hits occur during the last 300 seconds. In the worst case, all hits remain inside the active window.

Test Cases

from collections import deque
from typing import Deque

class HitCounter:

    def __init__(self):
        self.queue: Deque[int] = deque()

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

    def getHits(self, timestamp: int) -> int:
        while self.queue and timestamp - self.queue[0] >= 300:
            self.queue.popleft()

        return len(self.queue)

# Example case from problem statement
counter = HitCounter()
counter.hit(1)
counter.hit(2)
counter.hit(3)
assert counter.getHits(4) == 3  # all hits still valid

counter.hit(300)
assert counter.getHits(300) == 4  # timestamp 1 still counts

assert counter.getHits(301) == 3  # timestamp 1 expired

# Single hit
counter = HitCounter()
counter.hit(100)
assert counter.getHits(100) == 1  # immediate retrieval

# Expiration boundary
counter = HitCounter()
counter.hit(1)
assert counter.getHits(300) == 1  # still inside window
assert counter.getHits(301) == 0  # now expired

# Multiple hits at same timestamp
counter = HitCounter()
counter.hit(50)
counter.hit(50)
counter.hit(50)
assert counter.getHits(50) == 3  # duplicate timestamps handled

# No hits
counter = HitCounter()
assert counter.getHits(1) == 0  # empty structure

# Large timestamp values
counter = HitCounter()
counter.hit(2_000_000_000)
assert counter.getHits(2_000_000_000) == 1  # max constraint values

# Cleanup of many expired hits
counter = HitCounter()
for t in range(1, 10):
    counter.hit(t)

assert counter.getHits(400) == 0  # everything expired

# Sliding window behavior
counter = HitCounter()
counter.hit(1)
counter.hit(100)
counter.hit(200)
counter.hit(300)

assert counter.getHits(300) == 4  # all valid
assert counter.getHits(301) == 3  # timestamp 1 expired
assert counter.getHits(500) == 1  # only timestamp 300 remains
Test Why
Example from statement Validates official expected behavior
Single hit Verifies minimal non-empty case
Expiration boundary Confirms correct handling of 300 second edge
Multiple hits same timestamp Ensures duplicates are counted separately
No hits Verifies empty queue handling
Large timestamp values Confirms no overflow or comparison issues
Many expired hits Tests cleanup correctness
Sliding window behavior Validates rolling expiration logic

Edge Cases

Hits Exactly 300 Seconds Old

One of the easiest mistakes is incorrectly handling timestamps at the boundary of the 300 second window.

For example, a hit at timestamp 1 should still count when querying at timestamp 300, but should not count at timestamp 301.

The implementation handles this correctly using:

timestamp - old_timestamp >= 300

Only hits that are at least 300 seconds older are removed.

Multiple Hits at the Same Timestamp

The problem explicitly allows several hits to occur during the same second.

A buggy implementation might overwrite counts or accidentally deduplicate timestamps.

This solution stores every hit independently, so if three hits occur at timestamp 50, the queue contains:

[50, 50, 50]

The final count therefore remains accurate.

Empty Data Structure

Calling getHits before any hits have been recorded is another important edge case.

Without careful handling, removing expired timestamps from an empty queue could cause index errors.

The implementation safely checks:

while self.queue and ...

This guarantees that front access only happens when the queue is non-empty.

Large Gaps Between Queries

Suppose many hits are recorded early, and then a query happens much later.

Example:

hit(1)
hit(2)
hit(3)
getHits(1000)

All hits should expire.

The cleanup loop removes every outdated timestamp before returning the queue size, ensuring stale entries never remain permanently in memory.