Watch 10 video solutions for Design Hit Counter, a medium level problem involving Array, Binary Search, Design. This walkthrough by Happy Coding has 9,074 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 109timestamp is monotonically increasing).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?
Problem Overview: Design a data structure that records hits at specific timestamps and returns how many hits occurred in the last 5 minutes (300 seconds). The API exposes two operations: hit(timestamp) to record a hit and getHits(timestamp) to count hits within the sliding 300‑second window.
Approach 1: Queue / Sliding Window (O(n) worst case per query, O(n) space)
Store every hit timestamp in a queue. Each call to hit() pushes the timestamp into the queue. When getHits() runs, remove timestamps from the front while they are older than timestamp - 300. The remaining queue size equals the number of valid hits. This works because timestamps arrive in chronological order, so outdated entries always appear at the front. The approach relies on a simple sliding window using a queue, which keeps operations intuitive and efficient for moderate traffic streams.
Approach 2: Binary Search on Timestamp Array (O(log n) query, O(n) space)
Store timestamps in a dynamic array as hits arrive. Because timestamps are inserted in sorted order, the array remains sorted automatically. When getHits(timestamp) is called, compute the lower boundary timestamp - 299 and use binary search to find the first index whose timestamp falls within the 5‑minute window. The result equals total_hits - index. Recording a hit remains O(1), while queries run in O(log n). This approach works well for high query frequency since it avoids repeatedly popping elements.
The key insight is that timestamps are naturally ordered because the data stream is chronological. That property allows efficient searching over an array without additional sorting. Binary search quickly finds the earliest valid hit in the 300‑second window.
Recommended for interviews: The binary search design is usually the strongest answer. It demonstrates awareness of ordered data streams and efficient querying with logarithmic complexity. Mentioning the queue sliding‑window approach first shows you understand the problem constraints, but implementing the binary search solution highlights stronger algorithmic reasoning for scalable systems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Queue / Sliding Window | O(1) hit, O(n) worst‑case getHits | O(n) | Simple implementation when hit frequency is moderate and removing outdated timestamps is acceptable. |
| Binary Search on Timestamp Array | O(1) hit, O(log n) getHits | O(n) | Best when queries are frequent and timestamps remain sorted from the data stream. |