Design Hit Counter
Medium · Binary Search · Explanation and code example
Timestamped Circular Buckets
How it works
The query window covers the latest 300 seconds. Use timestamp modulo 300 to choose a bucket, and store the exact timestamp alongside its hit count. When a slot is reused by a newer second, reset it so stale hits cannot leak into the current window.
Steps
- On hit, reuse or reset the matching timestamp bucket.
- On getHits, sum buckets whose age is less than 300 seconds.
- Keep 300 timestamp and count slots.
Complexity
- Time: O(1) per hit; O(300) per query.
- Space: O(300).
Things to watch for
- At time 301, hits at time 1 have expired.
- Multiple hits at one timestamp accumulate.
- The problem guarantees calls use nondecreasing timestamps.
Python code example
class HitCounter:
def __init__(self):
self.timestamps = [0] * 300
self.hits = [0] * 300
def hit(self, timestamp: int) -> None:
i = timestamp % 300
if self.timestamps[i] == timestamp:
self.hits[i] += 1
else:
self.timestamps[i] = timestamp
self.hits[i] = 1 # Reset the hit count to 1.
def getHits(self, timestamp: int) -> int:
return sum(h for t, h in zip(self.timestamps, self.hits)
if timestamp - t < 300)
C++ code example
class HitCounter {
public:
void hit(int timestamp) {
const int i = timestamp % 300;
if (timestamps[i] == timestamp) {
++hits[i];
} else {
timestamps[i] = timestamp;
hits[i] = 1; // Reset the hit count to 1.
}
}
int getHits(int timestamp) {
int countHits = 0;
for (int i = 0; i < 300; ++i)
if (timestamp - timestamps[i] < 300)
countHits += hits[i];
return countHits;
}
private:
vector<int> timestamps = vector<int>(300);
vector<int> hits = vector<int>(300);
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.