MediumDesignQueueBinary Search

Design Hit Counter

1 approach, code in every language

Design a counter that records hits and, at any moment, can report how many hits occurred during the most recent five-minute window. Time is measured in seconds, and calls arrive in non-decreasing timestamp order.

Implement the class HitCounter. hit(timestamp) records that a hit happened at the given time in seconds. getHits(timestamp) returns the number of hits that occurred in the previous 300 seconds, meaning every recorded time t with timestamp minus 300 strictly less than t and t less than or equal to timestamp.

Several hits may share the same timestamp, and every hit must be counted individually.

Example 1

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

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

Hits at seconds 1, 2, and 3 give getHits(4) = 3. A hit at 300 makes getHits(300) = 4 since all four are within the window. By second 301 the hit at second 1 has expired, leaving 3.

Example 2

Input: operations = ["HitCounter", "hit", "getHits", "getHits"] args = [[], [1], [100], [400]]

Output: [null, null, 1, 0]

The single hit at second 1 is still counted at second 100, but by second 400 it has fallen outside the 300-second window.

Constraints

1 <= timestamp <= 2 * 10^9
All calls are made with a non-decreasing value of timestamp.
At most 300 calls will be made to hit and getHits.

Queue as a Sliding Window

Push each hit timestamp onto a queue and, when asked for a count, drop every timestamp that has aged past the 300-second window from the front.

Loading animation…

Intuition

Because timestamps arrive in non-decreasing order, the oldest hits are always at the front of a queue and the newest at the back. That means the only hits that can expire are the ones at the front, and once we discard an expired hit we never need to look at it again. When a count is requested, we repeatedly remove front timestamps that are at or before timestamp minus 300 until the front is fresh. Whatever remains in the queue is exactly the set of hits inside the current window, so its size is the answer.

Algorithm walkthrough

1Keep a queue of timestamps, ordered from oldest at the front to newest at the back.
2For hit(timestamp), append the timestamp to the back of the queue in constant time.
3For getHits(timestamp), inspect the front of the queue and remove it while its value is at or below timestamp minus 300.
4Stop removing as soon as the front timestamp lies strictly inside the window.
5Return the number of timestamps still in the queue, which are precisely the hits in the last 300 seconds.
6Since each timestamp is added once and removed at most once, the amortized cost of each call is constant.

Implementation

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)

Time

Amortized O(1) per hit and getHits, since each timestamp is enqueued once and dequeued at most once.

Space

O(n) where n is the number of hits still inside the current window.

If hits far outnumber window seconds, a fixed array of 300 second-buckets bounds memory to O(300).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free