Design Hit Counter

Problem in Plain English

Count how many hits landed in the trailing 300-second window ending at a query timestamp. Hits arrive in chronological order and several may share one timestamp.

Problem Statement

Design a hit counter that records hits and reports how many arrived in the past 5 minutes, meaning timestamps t with timestamp - t < 300.

The hit operation records one hit at a timestamp, and getHits returns the count of recorded hits inside the window ending at its timestamp. Calls arrive in chronological order, and several hits may share the same timestamp.

Constraints

$1 <= timestamp <= 2 * 10^9$
Timestamps arrive in non-decreasing chronological order.
A hit at t counts for queries with timestamp - t < 300.
At most 300 calls are made to hit and getHits.

Examples

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]

Hits at 1, 2, and 3 are all live at 4. After hit(300) the count at 300 is 4, and at 301 the hit from 1 expires, leaving 3.

Example 2

Input: ["HitCounter", "hit", "getHits", "getHits"] [[], [1], [4], [301]]
Output: [null, null, 1, 0]

The hit at 1 is inside the window at 4 since 4 - 1 < 300, but expired by 301 since 301 - 1 is not below 300.

Example 3

Input: ["HitCounter", "getHits", "hit", "hit", "getHits", "hit", "getHits", "getHits"] [[], [1], [1], [1], [300], [301], [301], [601]]
Output: [null, 0, null, null, 2, null, 1, 0]

An empty counter returns 0. Two hits at second 1 still count at second 300, age 299. At 301 they both expire exactly at age 300; the new hit at 301 replaces their modulo bucket and counts once. At 601 that hit also expires.

Intuition

At query time 301, the five-minute window contains seconds 2 through 301: the hit at 1 has just expired, while hits at 2, 3 and 300 remain. Chronological calls let a queue discard expired hits from its front. A stronger observation is that the window contains only 300 distinct integer seconds, so 300 stamped buckets can combine all hits sharing a second without confusing a reused bucket with its previous timestamp.

Approaches

Hit Queue

Solution Details

Reveal Hit Queue: intuition, complexity, and code

Intuition

Keep one timestamp per hit in arrival order, then remove expired timestamps only when a query needs the count. Because time never decreases, all expired hits form a prefix: at 301, removing 1 from [1, 2, 3, 300] leaves exactly the three live hits.

Step-by-Step Logic

Construct an empty queue; each hit appends its timestamp, preserving chronological order. In Example 1 the first three hits build [1, 2, 3].
For any getHits(timestamp), repeatedly remove the oldest hit while timestamp minus that hit is at least 300. The equality is essential: age 300 is outside the window.
At getHits(4), the oldest hit has age 3, so remove nothing and return the queue length 3. Append hit(300) to obtain [1, 2, 3, 300].
At getHits(300), the oldest hit has age 299, so return 4. At getHits(301), discard 1 at age 300; stop at 2 with age 299 and return 3.

Why It Works

The queue contains all recorded hits not yet discarded, in non-decreasing timestamp order. A query removes a front hit precisely when its age is at least 300. Once the front is younger than 300, every later hit is at least as recent and therefore live. Removed hits can never become live again because subsequent timestamps do not decrease. Thus the surviving queue length counts every live hit once, including multiple hits in the same second, and no expired hit.

Dry Run

Hit Queue: variable states at each step
Call	Oldest age / expiry work	Live queue after	Return
HitCounter()	no hits	[]	null
hit(1)	append	[1]	null
hit(2)	append	[1, 2]	null
hit(3)	append	[1, 2, 3]	null
getHits(4)	4 - 1 = 3; keep	[1, 2, 3]	3
hit(300)	append	[1, 2, 3, 300]	null
getHits(300)	300 - 1 = 299; keep	[1, 2, 3, 300]	4
getHits(301)	remove 1 at age 300; 2 has age 299	[2, 3, 300]	3

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the total hits recorded so far. A query may remove O(n) hits, so its worst-case time is O(n); hits use O(1) time in Java/Python and amortized O(1) append time in JavaScript. Across a sequence, each hit is appended once and discarded once, giving amortized O(1) work per call. Java/Python keep O(n) entries until a query evicts them, even if already expired. The JavaScript head-index queue retains all n historical array slots, including discarded entries, so its allocated storage remains O(n). A long run of hits without queries can grow every queue; time span alone does not bound hit multiplicity.

Code

Solution.java

1import java.util.LinkedList;2import java.util.Queue;3
4class HitCounter {5    private Queue<Integer> queue;6
7    public HitCounter() {8        queue = new LinkedList<>();9    }10
11    public void hit(int timestamp) {12        queue.offer(timestamp);13    }14
15    public int getHits(int timestamp) {16        // Age 300 is excluded; chronological order makes expired hits a prefix.17        while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {18            queue.poll();19        }20        return queue.size();21    }22}

Hints

Hint 1

Because timestamps never go backward, the oldest stored hit is always at the front of a queue.

Hint 2

Storing every hit separately wastes space when thousands share one timestamp, so group hits by their second.

Hint 3

Map each timestamp to one of 300 buckets with timestamp % 300, and stamp each bucket so a collision with an old window is detected instead of double counted.

Edge Cases

No hits yet: zero counts make getHits return 0, even when unused stamp 0 is younger than 300.
A hit at t counts at t + 299 but expires exactly at t + 300.
Repeated hits at the same second must all count; equal query timestamps leave the answer unchanged until another hit.
Modulo collisions such as 1 and 301 reset the bucket, while a gap of several full windows makes every old stamp stale.
Timestamps near 2000000000 remain safe for Java int subtraction under the positive timestamp constraint.

Common Mistakes and Interview Tips

Evicting with timestamp - front > 300 instead of >= 300, which keeps a hit that is exactly 300 old.
Reusing a collided bucket without comparing stamps, which mixes the old window count into the new one.
Resetting the count on every hit instead of only when the stamp differs, which erases same-second bursts.
Assuming the queue uses only 300 entries: arbitrarily many hits may share one second, and the JavaScript head-index version also retains expired slots.
Interview tip: distinguish O(n) worst-case queue query time from amortized constant work, then prove why modulo collisions cannot discard any live hit.

Key Takeaway

A fixed window over ordered time folds into a circular buffer: modulo indexing bounds the memory while stored stamps separate the current window from ghosts.