Skip to content

362. Design Hit Counter

On LeetCode ->

Problem

Design HitCounter with chronologically ordered calls; equal timestamps are allowed.

  • hit(t) records a hit at second t.
  • getHits(t) counts hits whose timestamps satisfy \(t - 300 < s \le t\).
  • Support many hits at the same second without storing each separately.
Calls:   hit(1), hit(1), hit(300), getHits(300), getHits(301)
Returns:   -       -        -          3             1

class HitCounter:
    def __init__(self):
        pass

    def hit(self, timestamp: int) -> None:
        pass

    def getHits(self, timestamp: int) -> int:
        pass

Key trick

Keep a deque of (timestamp, count) buckets and a running total; subtract expired buckets before either operation.

Trap

A hit exactly 300 seconds old is expired, and "monotonically increasing" here means nondecreasing: repeated timestamps are valid.

Why is it interesting?

It combines sliding-window expiration with aggregation, making storage independent of the number of hits per second.

Python solution

from collections import deque


class HitCounter:
    def __init__(self):
        self.q = deque()
        self.total = 0

    def _expire(self, timestamp: int) -> None:
        # The window excludes timestamp - 300.
        while self.q and self.q[0][0] <= timestamp - 300:
            _, cnt = self.q.popleft()
            self.total -= cnt

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

        # Aggregate simultaneous hits instead of storing each hit.
        if self.q and self.q[-1][0] == timestamp:
            _, cnt = self.q[-1]
            self.q[-1] = (timestamp, cnt + 1)
        else:
            self.q.append((timestamp, 1))

        self.total += 1

    def getHits(self, timestamp: int) -> int:
        self._expire(timestamp)
        return self.total
  • Time: \(O(1)\) amortized per call; \(O(300)\) worst case when expiring buckets.
  • Space: \(O(300)\), with at most one bucket per second in the window.

Comment on my solution

Your deque of aggregated timestamps is the right approach; the stub is unfinished.

  • Maintain total: increment on each hit and subtract each expired bucket's count.
  • No timestamp-to-index map is needed.
  • A query timestamp need not exist in the deque: it only determines which buckets expire.
  • Cumulative sums alone would retain unnecessary history and require searching for the window boundary.
# Ideas
# - need some sort of counter
# - maybe do cumulative sum??
# - keep number of hit per second (per timestamp)
# - I'm not sure about "monotonically increasing",
#   does this allow repeated number like 1, 2, 2, 3
# - how to avoid scanning all last 300 seconds?
# [. . .. . .. ... .]
# - keep sliding window of (timestamp, hits)
#   - when new hit updated last pushed tuple if same timestamp
#   - deque old tuple no longer in 300 span window
#   - count total hit in queue and store result for last timestamp
#     - but how?
#       - with a list + a map of timestamp to index in that list
#   - This doesn't work because when getHits() with a non existing
#     timestamp, we can count the hits, because that have been aggregated
#     in other timestamp

from collections import deque

class HitCounter:
    def __init__(self):

    def hit(self, timestamp: int):

    def getHits(self, timestamp: int):

Extra

Problem description

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

  • HitCounter() Initializes the object of the hit counter system.
  • void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
  • int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

Example 1:

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

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

Constraints:

  • 1 <= timestamp <= 2 * 10^9
  • All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).
  • At most 300 calls will be made to hit and getHits.

Follow up: What if the number of hits per second could be huge? Does your design scale?

Clarification of the problem description

I think there something I didn't get in the problem description. If we received hit(500), can I ask after for getHits(300)? This is what I understood, and in that case the sliding window alone with total is not enough because it didn't store all hit history.

Yes: the chronological-order guarantee applies to all calls, including both hit and getHits.

After hit(500), calling getHits(300) is not allowed.

# Valid: timestamps never decrease.
counter.hit(500)
counter.getHits(500)
counter.getHits(600)
counter.hit(600)

# Invalid: time moves backward.
counter.hit(500)
counter.getHits(300)

Here, "monotonically increasing" means nondecreasing: equal timestamps are allowed.

That guarantee makes the sliding window safe: once a hit expires, no future valid query can include it. Your concern would be correct if historical queries were allowed; that would require a different design that preserves history.