Design Hit Counter

Medium

Problem

Design a counter with hit(timestamp) and getHits(timestamp), which returns the number of hits in the past 300 seconds (timestamps in (t − 300, t]). Timestamps are in seconds and arrive in non-decreasing order.

Example 1

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

Test cases

Case 1

Input:    new HitCounter()
.hit(1)
.hit(2)
.hit(3)
.getHits(4)
.hit(300)
.getHits(300)
.getHits(301)
Expected: [null,null,null,3,null,4,3]

Case 2

Input:    new HitCounter()
.hit(1)
.hit(1)
.getHits(1)
.getHits(300)
.getHits(301)
Expected: [null,null,2,2,0]

Case 3

Input:    new HitCounter()
.getHits(1)
Expected: [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Queue of timestamps

Time O(1) amortisedSpace O(hits in the window)

Push each hit; on getHits drop timestamps older than 300 s from the front.

class HitCounter {
constructor() { this.q = []; this.head = 0; }
hit(t) { this.q.push(t); }
getHits(t) {
while (this.head < this.q.length && this.q[this.head] <= t - 300) this.head++;
return this.q.length - this.head;
}
}

2. Fixed 300-slot ring buffer

Time hit O(1), getHits O(300)Space O(300)

Bounded memory under heavy traffic: slot t % 300 stores [time, count]; reset a slot when its time is stale.

class HitCounter {
constructor() { this.times = new Array(300).fill(0); this.counts = new Array(300).fill(0); }
hit(t) {
const i = t % 300;
if (this.times[i] !== t) { this.times[i] = t; this.counts[i] = 0; }
this.counts[i]++;
}
getHits(t) {
let total = 0;
for (let i = 0; i < 300; i++) if (t - this.times[i] < 300) total += this.counts[i];
return total;
}
}

The follow-up "what if hits per second are huge?" is asking for this version.