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

Implement HitCounter:

  • HitCounter() – initializes the counter
  • void hit(int timestamp) – records a hit at the given timestamp
  • int getHits(int timestamp) – returns the number of hits in the past 300 seconds (i.e., [timestamp - 299, timestamp])

Timestamps are in increasing order (though ties are allowed).

Examples

Example 1:

Input:
  hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301)

Output:
  null, null, null, 3, null, 4, 3

Explanation:
  getHits(4):   hits at 1,2,3 → 3
  getHits(300): hits at 1,2,3,300 → 4
  getHits(301): hit at 1 is outside [2,301] → hits at 2,3,300 → 3

Constraints

  • 1 <= timestamp <= 2 * 10^9
  • All calls to hit and getHits are made with strictly increasing timestamp (with ties allowed for hit)
  • At most 300 calls to hit and getHits

Thinking Process

We need a sliding window of hits within the last 300 seconds. The key question is: how do we efficiently expire old hits?

Since timestamps arrive in non-decreasing order, older hits are always at the front – a natural fit for a queue/deque.

Sliding window a b c d e window expand right, shrink left when invalid

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Solution

Use a deque to store timestamps. On getHits, pop from the front while the oldest hit is outside the window.

class HitCounter {
public:
    HitCounter() {}

    void hit(int timestamp) {
        hits.push_back(timestamp);
    }

    int getHits(int timestamp) {
        while (!hits.empty() && hits.front() <= timestamp - 300) {
            hits.pop_front();
        }
        return hits.size();
    }

private:
    deque<int> hits;
};

Solution Explanation

Approach: Fixed-size window (this problem)

Key idea: We need a sliding window of hits within the last 300 seconds. The key question is: how do we efficiently expire old hits?

Walkthrough — input hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301), expected output null, null, null, 3, null, 4, 3:

getHits(4): hits at 1,2,3 → 3 getHits(300): hits at 1,2,3,300 → 4 getHits(301): hit at 1 is outside [2,301] → hits at 2,3,300 → 3

Comparison

Approach hit getHits Best For
Deque O(1) amortized O(1) Timestamps in order (this problem)
Sorted Vector O(n) worst / O(1) practical O(log n + k) Random access needed
Multiset O(log n) O(k log n) Timestamps out of order

Common Mistakes

  • Using < timestamp - 300 instead of <= timestamp - 300 (the window is exactly 300 seconds: [timestamp - 299, timestamp])
  • Not handling duplicate timestamps (multiple hits at the same time)
  • Over-engineering with a hash map when a simple queue suffices

Key Takeaways

  • Sliding time window + ordered arrivals = deque is the natural data structure
  • Each element is enqueued and dequeued at most once, giving amortized O(1) per operation
  • The deque solution is the expected interview answer for this problem – clean, simple, and optimal

References

Template Reference