How do you approach Design Hit Counter?

Store each hit's timestamp in a queue (FIFO). Because timestamps arrive in non-decreasing order, the queue stays sorted automatically.

What is the time complexity of Design Hit Counter?

Time complexity: O(1) amortized per operation across the whole sequence.. Space complexity: O(n) in the worst case, bounded by the number of hits inside the active window..

What are common mistakes on Design Hit Counter?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Design Hit Counter

MediumObject-Oriented Design

Description

Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds).

hit(timestamp) records a hit at the given timestamp (in seconds).
getHits(timestamp) returns the number of hits in the past 300 seconds. A hit at time t counts toward a query at timestamp if t > timestamp - 300 (the trailing 300-second window, exclusive of the boundary).

Hits and queries are issued in non-decreasing timestamp order.

Implement the function hitCounter(operations) where operations is a list of [op, ...args]: ["hit", timestamp] and ["getHits", timestamp]. For "hit" return null; for "getHits" return the count. Return the list of results, one per operation (use null for operations that return nothing).

Example 1

Input: operations = [["hit",1],["hit",2],["hit",3],["getHits",4],["hit",300],["getHits",300],["getHits",301]]

Output: [null, null, null, 3, null, 4, 3]

Example 2

Input: operations = [["getHits",1],["hit",1],["getHits",1],["getHits",300],["getHits",301]]

Output: [0, null, 1, 1, 0]

Example 3

Input: operations = [["hit",1],["hit",1],["hit",1],["getHits",1],["getHits",50]]

Output: [null, null, null, 3, 3]

Constraints

1 <= timestamp <= 2*10^9. Operations arrive with non-decreasing timestamps. At most 10000 operations. Several hits may share the same timestamp.

Design Hit Counter: approach, complexity and pitfalls

A medium design problem, graded against 6 test cases (3 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

Store each hit's timestamp in a queue (FIFO). Because timestamps arrive in non-decreasing order, the queue stays sorted automatically.
On getHits(timestamp), evict every hit from the front whose timestamp is <= timestamp - 300, since those fall outside the trailing 300-second window. The remaining count is the answer.
Be careful with the boundary: a hit at exactly timestamp - 300 is NOT counted (the window is t > timestamp - 300). A hit at timestamp - 299 is counted.

The optimal approach

Show the approach: The approach

Keep a queue of hit timestamps. Since hits arrive in non-decreasing order, the queue is naturally sorted. For `getHits(timestamp)`, pop from the front while the front timestamp is `<= timestamp - 300` (those are too old), then the queue length is the number of hits in the trailing 300-second window. Each timestamp is enqueued once and dequeued at most once.

Time: O(1) amortized per operation across the whole sequence.
Space: O(n) in the worst case, bounded by the number of hits inside the active window.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.