Skip to main content
CodePeet

Design Hit Counter

Try it yourself
MediumProblemExternal link

Description

Design a hit counter that counts the hits received in the past 5 minutes, the past 300 seconds.

Implement the HitCounter class:

  • HitCounter() starts a counter with no hits.
  • void hit(int timestamp) records a hit at timestamp, in seconds. Several hits can come in the same second.
  • int getHits(int timestamp) returns the number of hits in the past 5 minutes from timestamp: those less than 300 seconds before it.

The calls come in time order: each timestamp is at least the one before.

Follow-up: what if the number of hits per second could be huge? Does your design scale?

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]

Explanation: At 4 the hits at 1, 2 and 3 are all in the last 300 seconds. With one more at 300, getHits(300) counts 4. At 301 the hit at 1 is exactly 300 seconds old, so it's out: 3.

Example 2

Input:

["HitCounter", "hit", "hit", "hit", "hit", "getHits", "getHits", "getHits"]
[[], [10], [10], [10], [20], [309], [310], [320]]

Output: [null, null, null, null, null, 4, 1, 0]

Explanation: Three hits come in the same second, 10, and each one counts. At 309 they're 299 seconds old, still in: 4. At 310 they're out, leaving the hit at 20, and at 320 that one is out too.

Example 3

Input:

["HitCounter", "getHits", "hit", "hit", "getHits", "getHits", "getHits"]
[[], [1], [5], [305], [305], [604], [605]]

Output: [null, 0, null, null, 1, 1, 0]

Explanation: Nothing has come in at 1. At 305 the hit at 5 is exactly 300 seconds old, so only the hit at 305 counts; it is still in at 604 and out at 605.

Constraints

  • 1 ≤ timestamp ≤ 2 × 10⁹
  • The calls come in time order: timestamps never decrease
  • At most 300 calls are made to hit and getHits

Editorial

Brute Force

Intuition

Keep every hit's time in a list. For getHits, read the whole list and count the times less than 300 seconds before the question.

Step-by-Step Explanation

Let's trace Example 1:

  1. hit(1) adds 1 to the list, which keeps every hit.
  2. hit(2) adds 2 to the list, which keeps every hit.
  3. hit(3) adds 3 to the list, which keeps every hit.
  4. getHits(4) reads all 3 hits and counts 3 less than 300 seconds old.
  5. hit(300) adds 300 to the list, which keeps every hit.
  6. getHits(300) reads all 4 hits and counts 4 less than 300 seconds old.
  7. getHits(301) reads all 4 hits and counts 3 less than 300 seconds old; the hit at 1 is out.

Every Hit in a List — Hits pile up for good; each question reads all of them and counts the recent ones.

Algorithm

  1. hit appends timestamp to a list.
  2. getHits counts the times t in the list with timestamp - t < 300.

Code

class HitCounter {
    vector<int> times;                        // every hit, kept for good
public:
    HitCounter() {
    }

    void hit(int timestamp) {
        times.push_back(timestamp);
    }

    int getHits(int timestamp) {
        int n = 0;
        for (int t : times)                   // read them all
            if (timestamp - t < 300) n++;
        return n;
    }
};

class HitCounter:
    def __init__(self):
        self.times = []                       # every hit, kept for good

    def hit(self, timestamp: int) -> None:
        self.times.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        return sum(1 for t in self.times if timestamp - t < 300)   # read them all

class HitCounter {
    private final List<Integer> times = new ArrayList<>();     // every hit, kept for good

    public HitCounter() {
    }

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

    public int getHits(int timestamp) {
        int n = 0;
        for (int t : times)                   // read them all
            if (timestamp - t < 300) n++;
        return n;
    }
}

var HitCounter = function() {
    this.times = [];                          // every hit, kept for good
};

HitCounter.prototype.hit = function(timestamp) {
    this.times.push(timestamp);
};

HitCounter.prototype.getHits = function(timestamp) {
    let n = 0;
    for (const t of this.times) if (timestamp - t < 300) n++;   // read them all
    return n;
};

Complexity Analysis

Time Complexity: O(1) for hit, O(n) for getHits

A question reads all n hits ever made.

Space Complexity: O(n)

The list keeps every hit for good.

Why This Approach Is Not Efficient

At the problem's 300 calls anything is fast. A counter in a running service isn't stopped there: on 10,000 hits one second apart, each followed by getHits, the list took 2.64 s in Python on the judge, against 92 ms for the queue below. The list ends up holding all 10,000 hits, though never more than 300 of them can be in a window. The times come in order, so once a hit is 300 seconds old it's out for good: drop it.

Optimal Approach - A Queue of Recent Hits

Intuition

The times arrive in order, so keep them in a queue, oldest first. Every call first drops the times at the front that are 300 seconds old or more; what's left is exactly the window, and getHits returns its size. Each hit enters the queue once and leaves it once.

Step-by-Step Explanation

Let's trace Example 1 again:

  1. hit(1): 1 joins the back of the queue.
  2. hit(2): 2 joins the back of the queue.
  3. hit(3): 3 joins the back of the queue.
  4. getHits(4): 3 times are left, and that's the answer.
  5. hit(300): 300 joins the back of the queue.
  6. getHits(300): 4 times are left, and that's the answer.
  7. getHits(301): the hit at 1 leaves the front first, 300 seconds old or more. 3 times are left, and that's the answer.

A Queue of Recent Hits — Each call first drops the hits 300 seconds old from the front; the rest is the answer.

Algorithm

  1. Keep a queue of hit times, oldest first.
  2. Each call first drops the front while it's at or before timestamp - 300.
  3. hit then adds timestamp at the back; getHits returns the queue's size.

Code

class HitCounter {
    deque<int> times;                         // the hit times of the last 300 seconds, oldest first

    void dropOld(int timestamp) {
        while (!times.empty() && times.front() <= timestamp - 300) times.pop_front();
    }

public:
    HitCounter() {
    }

    void hit(int timestamp) {
        dropOld(timestamp);
        times.push_back(timestamp);
    }

    int getHits(int timestamp) {
        dropOld(timestamp);
        return times.size();
    }
};

from collections import deque


class HitCounter:
    def __init__(self):
        self.times = deque()                  # the hit times of the last 300 seconds, oldest first

    def drop_old(self, timestamp):
        while self.times and self.times[0] <= timestamp - 300:   # 300 seconds old or more: out of the window
            self.times.popleft()

    def hit(self, timestamp: int) -> None:
        self.drop_old(timestamp)
        self.times.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        self.drop_old(timestamp)
        return len(self.times)

class HitCounter {
    private final Deque<Integer> times = new ArrayDeque<>();   // the hit times of the last 300 seconds, oldest first

    public HitCounter() {
    }

    private void dropOld(int timestamp) {
        while (!times.isEmpty() && times.peekFirst() <= timestamp - 300) times.pollFirst();
    }

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

    public int getHits(int timestamp) {
        dropOld(timestamp);
        return times.size();
    }
}

var HitCounter = function() {
    this.times = [];                          // hit times, oldest first; the ones before head are dropped
    this.head = 0;
};

HitCounter.prototype.dropOld = function(timestamp) {
    while (this.head < this.times.length && this.times[this.head] <= timestamp - 300) this.head++;
    if (this.head > 64 && 2 * this.head > this.times.length) {   // let go of the dropped half
        this.times = this.times.slice(this.head);
        this.head = 0;
    }
};

HitCounter.prototype.hit = function(timestamp) {
    this.dropOld(timestamp);
    this.times.push(timestamp);
};

HitCounter.prototype.getHits = function(timestamp) {
    this.dropOld(timestamp);
    return this.times.length - this.head;
};

Complexity Analysis

Time Complexity: O(1) per call, amortized

Each hit is added once and dropped once over all the calls.

Space Complexity: O(w)

The w hits of the last 300 seconds.

Follow-Up - A Ring of 300 Buckets

Intuition

The queue keeps one entry per hit: a million hits a second is a million entries a second. But a question only needs how many hits came in each of the last 300 seconds. Keep 300 buckets, one for each t % 300, each holding the second it last counted and its hits. A hit goes to its bucket, and if that bucket still counts a second 300 or more seconds gone, it starts over first. getHits adds up the buckets whose second is in the window.

Step-by-Step Explanation

Let's trace Example 3, where two hits 300 seconds apart share a bucket:

  1. getHits(1): no bucket's second is less than 300 seconds before 1, so the answer is 0.
  2. hit(5) goes to bucket 5 % 300 = 5, and counts 1 hit at second 5.
  3. hit(305) goes to bucket 305 % 300 = 5, which last counted second 5, 300 or more seconds ago, so it starts over at 1 hit.
  4. getHits(305) adds up the buckets whose second is less than 300 seconds before 305: bucket 5's 1, 1 in all.
  5. getHits(604) adds up the buckets whose second is less than 300 seconds before 604: bucket 5's 1, 1 in all.
  6. getHits(605): no bucket's second is less than 300 seconds before 605, so the answer is 0.

A Ring of 300 Buckets — The buckets in use, each with its hits at the second it counts; a bucket reused 300 seconds later starts over.

Algorithm

  1. Keep two arrays of 300: second[b], the second bucket b last counted, and count[b], its hits.
  2. hit: with b = timestamp % 300, if second[b] isn't timestamp, set it to timestamp and count[b] to 0; then add 1 to count[b].
  3. getHits: add up count[b] for every bucket with timestamp - second[b] < 300.

Code

class HitCounter {
    int second[300] = {}, count[300] = {};    // bucket t % 300: the second it last counted, and its hits
public:
    HitCounter() {
    }

    void hit(int timestamp) {
        int b = timestamp % 300;
        if (second[b] != timestamp) {         // that second is 300 or more seconds gone: start the bucket over
            second[b] = timestamp;
            count[b] = 0;
        }
        count[b]++;
    }

    int getHits(int timestamp) {
        int total = 0;
        for (int b = 0; b < 300; b++)
            if (timestamp - second[b] < 300) total += count[b];
        return total;
    }
};

class HitCounter:
    def __init__(self):
        self.second = [0] * 300               # bucket t % 300: the second it last counted
        self.count = [0] * 300                # and how many hits came in that second

    def hit(self, timestamp: int) -> None:
        b = timestamp % 300
        if self.second[b] != timestamp:       # that second is 300 or more seconds gone: start the bucket over
            self.second[b], self.count[b] = timestamp, 0
        self.count[b] += 1

    def getHits(self, timestamp: int) -> int:
        return sum(c for s, c in zip(self.second, self.count) if timestamp - s < 300)

class HitCounter {
    private final int[] second = new int[300], count = new int[300];   // bucket t % 300: its second and its hits

    public HitCounter() {
    }

    public void hit(int timestamp) {
        int b = timestamp % 300;
        if (second[b] != timestamp) {         // that second is 300 or more seconds gone: start the bucket over
            second[b] = timestamp;
            count[b] = 0;
        }
        count[b]++;
    }

    public int getHits(int timestamp) {
        int total = 0;
        for (int b = 0; b < 300; b++)
            if (timestamp - second[b] < 300) total += count[b];
        return total;
    }
}

var HitCounter = function() {
    this.second = new Array(300).fill(0);     // bucket t % 300: the second it last counted
    this.count = new Array(300).fill(0);      // and how many hits came in that second
};

HitCounter.prototype.hit = function(timestamp) {
    const b = timestamp % 300;
    if (this.second[b] !== timestamp) {       // that second is 300 or more seconds gone: start the bucket over
        this.second[b] = timestamp;
        this.count[b] = 0;
    }
    this.count[b]++;
};

HitCounter.prototype.getHits = function(timestamp) {
    let total = 0;
    for (let b = 0; b < 300; b++) if (timestamp - this.second[b] < 300) total += this.count[b];
    return total;
};

Complexity Analysis

Time Complexity: O(1) for hit, O(300) for getHits

A question reads the 300 buckets, a constant however many hits came.

Space Complexity: O(300)

Two arrays of 300, whatever the number of hits a second.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Counting a hit exactly 300 seconds old. while self.times and self.times[0] < timestamp - 300:

On Example 1 it returns [null, null, null, null, 3, null, 4, 4]; the answer is [null, null, null, null, 3, null, 4, 3]. The past 5 minutes are the 300 seconds before the question: a hit at t − 300 is 300 seconds old and out. Dropping only the times before t − 300 keeps it one second too long.

getHits not dropping old hits. return len(self.times)

On Example 2 it returns [null, null, null, null, null, 4, 4, 4]; the answer is [null, null, null, null, null, 4, 1, 0]. The window moves with every question, not only with every hit. If only hit drops the old times, a question that comes long after the last hit still counts hits that left the window.

A ring of buckets that never starts over. self.count[timestamp % 300] += 1

On Example 3 it returns [null, 0, null, null, 2, 2, 2]; the answer is [null, 0, null, null, 1, 1, 0]. The follow-up keeps 300 buckets, one for each t % 300, and a bucket is shared by seconds exactly 300 apart. Without the second it last counted, a bucket adds a new hit to the count of a second that left the window long ago.

Where This Pattern Is Taught

This problem practises keeping only the part of the history a question can still reach: a queue that drops what falls out of the window, or a ring of buckets when the hits are too many to keep one by one. It's taught in Designing with History.