362. Design Hit Counter

362

MediumData Structure DesignMonotonic queue of timestampsSliding time window

Design Hit Counter

Design a hit counter that counts hits received in the past 5 minutes (300 seconds). hit(timestamp) records a hit at the given time in seconds. getHits(timestamp) returns how many hits happened in the previous 300 seconds, i.e. with time in the range (timestamp - 300, timestamp]. Calls arrive in non-decreasing timestamp order; several hits may share a timestamp.

Open official problem prompt ↗

In plain English

Report how many hits landed within the most recent 300-second window ending at the query time.

Picture it like this

Like a turnstile counter that only cares about the last five minutes: as time moves forward, entries older than five minutes silently roll off the tally.

Example

Input: hit(1); hit(2); hit(3); getHits(4); hit(300); getHits(300); getHits(301)
Output: 3; 4; 3
Why: At time 4 the hits at 1,2,3 count (=3); at 300 all four count (=4); at 301 the hit at time 1 falls outside (301-300=1, so 1 is excluded), leaving 3.

Constraints

1 <= timestamp <= 2 * 10^9All calls are made in non-decreasing timestamp orderAt most 300 hits per second in the follow-up variantAt most 3 * 10^4 calls to hit and getHits

Pattern lesson

See the pattern, then code

Sliding time window

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Since timestamps only increase, hits older than timestamp - 300 can never count again, so evict them from the front of a queue and the queue's length is the answer.

New words, made simpleKnow these before the algorithm

Sliding window: A fixed-length interval (300s) whose right edge is the current query time.
FIFO queue: First-in-first-out structure; oldest timestamps sit at the front and expire first.
Amortized cost: Averaged cost per operation - each hit is enqueued once and dequeued once overall.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Scan a full list of timestamps

Rescans all history and never frees expired hits.

Keep every timestamp and, on each query, count those within the window.

Time O(n) per querySpace O(n) unbounded

Best choiceFront-evicting queue

Each hit is touched twice total and memory is bounded by the window.

Enqueue timestamps; on query, drop expired ones from the front and return the size.

Time Amortized O(1) per hit, O(k) per querySpace O(window) hits

The rule we keep true

Invariant

After any getHits(t), the queue contains exactly the timestamps in (t - 300, t] in increasing order.

Why this is correct

Reasoning

Timestamps arrive non-decreasing, so once a timestamp is <= t - 300 it can never re-enter any future window; removing it from the front is permanently safe, and the surviving count is exactly the window's hit total.

The algorithm in three movesSay these aloud before coding

1On hit, append the timestamp to the back of a queue

queue = [1,2,3,300]

2On getHits, pop from the front every timestamp <= current - 300

getHits(301): pop 1 (1 <= 1)

3The remaining queue length is the number of hits in the window

queue = [2,3,300] -> 3

4Because timestamps are non-decreasing, each hit is evicted at most once

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

3003

1 · Readthree hits

2 · Askstore where?

3 · Update statequeue=[1,2,3]

4 · Resultrecorded

Key takeaway

At time 301 the timestamp 1 has expired and is removed, leaving three hits in the window.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 1-5State
A deque of timestamps supports O(1) append at the back and pop at the front.
2
Lines 7-8hit
Just append; the timestamp is the most recent and belongs at the back.
3
Lines 10-13getHits
Evict everything at or before timestamp - 300, then the remaining length is the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A hit exactly at timestamp - 300 is excluded (boundary is open on the old side)
getHits before any hit returns 0
Many hits sharing one timestamp all count while inside the window
Large timestamp gaps clear the whole queue at once

Common beginner mistakes

Using < instead of <= when expiring, keeping a hit that is exactly 300 seconds old
Assuming one hit per timestamp - duplicates are allowed
Not exploiting the non-decreasing guarantee and re-sorting
For very high hit rates, an unbounded queue may be worse than the fixed 300-bucket array variant

Check your understanding

Why is popping expired timestamps from the front amortized O(1) rather than O(n) per query?

Design Hit Counter

Design Hit Counter

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design