Design Hit Counter

Medium Design Data Structures Queue / Circular Buffer Original on LeetCode

Design Hit Counter is a medium design data structures problem solved with the queue / circular buffer pattern. The best approach, optimal (300 circular buckets), runs in O(1) per hit, O(300) per getHits time and O(300) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (keep every hit) up.

Problem

Build a class HitCounter that counts how many hits (events) happened in the last 5 minutes, that is, the last 300 seconds. HitCounter() creates a counter with no hits.

hit(int timestamp) records one hit at second timestamp. getHits(int timestamp) returns how many recorded hits happened in the window from timestamp - 299 to timestamp, inclusive: a hit at second s counts when timestamp - s < 300.

Calls arrive in chronological order, so timestamps never decrease, but several hits may happen in the same second.

Examples

Example 1

Input
HitCounter(), hit(10), hit(10), hit(200), getHits(250), getHits(309), getHits(310), getHits(500)
Output
3, 3, 1, 0
Why
At 309 the window is 10..309, so both hits at 10 still count; at 310 it starts at 11 and they drop out. At 500 the window is 201..500, so the hit at 200 has expired too.

Example 2

Input
HitCounter(), hit(1), hit(2), hit(300), getHits(300), hit(301), getHits(301), getHits(600)
Output
3, 3, 1
Why
At 301 the hit at 1 leaves the window (2..301) while the new hit joins it; at 600 the window is 301..600, so only the hit at 301 is left.

Constraints

  • 1 <= timestamp <= 2 * 10^9
  • Calls are made in chronological order: each timestamp is greater than or equal to the previous one.
  • Several hits can share the same timestamp.
  • At most 3 * 10^4 calls to hit and getHits in total.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (keep every hit)O(1) per hit, O(total hits) per getHitsO(total hits)
Better (queue of recent hits)O(1) amortized per callO(hits in the last 300 seconds)
Optimal (300 circular buckets)O(1) per hit, O(300) per getHitsO(300)

1Brute force (keep every hit)

TimeO(1) per hit, O(total hits) per getHitsEvery query walks the full history of hits.
SpaceO(total hits)Old hits are never removed.

Append every hit time to a list and never delete anything. To answer getHits(t), scan the whole list and count the times s with t - s < 300.

  1. hit(t): append t to the list.
  2. getHits(t): count the stored times s with s > t - 300 and return the count.
class HitCounter {
    private final List<Integer> hits = new ArrayList<>();

    public HitCounter() {}

    public void hit(int timestamp) {
        hits.add(timestamp);
    }

    public int getHits(int timestamp) {
        int count = 0;
        for (int s : hits) {
            if (timestamp - s < 300) count++;
        }
        return count;
    }
}

2Better (queue of recent hits)

TimeO(1) amortized per callEach hit is pushed once and popped at most once over the whole run.
SpaceO(hits in the last 300 seconds)Only hits that can still count stay in the queue, but a burst of many hits in one second keeps them all.

Because time only moves forward, the oldest hit is always the first to expire. Keep hits in a queue; whenever a call arrives, drop hits from the front while they are 300 or more seconds old. The queue size is then the answer.

  1. hit(t): push t to the back of the queue.
  2. getHits(t): while the queue is not empty and t - front >= 300, pop the front.
  3. Return the queue size.
class HitCounter {
    private final Deque<Integer> queue = new ArrayDeque<>();

    public HitCounter() {}

    public void hit(int timestamp) {
        queue.addLast(timestamp);
    }

    public int getHits(int timestamp) {
        while (!queue.isEmpty() && timestamp - queue.peekFirst() >= 300) {
            queue.pollFirst();
        }
        return queue.size();
    }
}

3Optimal (300 circular buckets)

TimeO(1) per hit, O(300) per getHitsA hit touches one bucket; a query looks at all 300, a constant.
SpaceO(300)Two fixed arrays of 300 numbers, independent of the number of hits.

Only the last 300 seconds matter, and two seconds in that window never share the same value of timestamp % 300. So keep 300 buckets; bucket t % 300 stores which second it currently describes and how many hits happened then. A hit either adds to its bucket or, if the bucket still holds an older second, resets it. A query sums the buckets whose second is still inside the window. Memory stays fixed no matter how many hits arrive per second.

  1. times[300] and counts[300], all 0.
  2. hit(t): i = t % 300; if times[i] != t, set times[i] = t and counts[i] = 1; otherwise counts[i]++.
  3. getHits(t): add counts[i] for every i with t - times[i] < 300 (and times[i] set).
class HitCounter {
    private final int[] times = new int[300];
    private final int[] counts = new int[300];

    public HitCounter() {}

    public void hit(int timestamp) {
        int i = timestamp % 300;
        if (times[i] != timestamp) {
            times[i] = timestamp;
            counts[i] = 1;
        } else {
            counts[i]++;
        }
    }

    public int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; i++) {
            if (times[i] > 0 && timestamp - times[i] < 300) total += counts[i];
        }
        return total;
    }
}

Edge cases to test

  • getHits before any hit returns 0
  • Many hits at the same second must all be counted
  • A hit exactly 299 seconds old still counts; one exactly 300 seconds old does not
  • Long gaps between calls: everything old must expire, even if no call happened in between

Hints

Hint 1

At time t, a hit at time s counts exactly when t - s < 300. Since timestamps only grow, once a hit is too old it stays too old forever.

Hint 2

Keep the hits in a queue in arrival order; before answering, pop from the front while the front is too old.

Hint 3

For constant memory, note that only the last 300 seconds matter: keep 300 buckets indexed by timestamp % 300, each remembering which second it currently holds and how many hits it has.

FAQ

What is the best time complexity for Design Hit Counter?

Optimal (300 circular buckets) runs in O(1) per hit, O(300) per getHits time and O(300) extra space. A hit touches one bucket; a query looks at all 300, a constant.

Which pattern does Design Hit Counter use?

It is a design data structures problem that uses the queue / circular buffer pattern. Other problems with the same pattern: Design Circular Queue, First Unique Number, Design Snake Game.

Is there a brute force solution for Design Hit Counter?

Yes. Brute force (keep every hit) takes O(1) per hit, O(total hits) per getHits time and O(total hits) space. Append every hit time to a list and never delete anything.

Which edge cases should I test for Design Hit Counter?

getHits before any hit returns 0; Many hits at the same second must all be counted; A hit exactly 299 seconds old still counts; one exactly 300 seconds old does not; Long gaps between calls: everything old must expire, even if no call happened in between.