228. Design Hit Counter

Keep hits in a queue. On getHits, drop everything older than 300 seconds from the front; the queue size is the answer.

Sliding 300-second window

Store each hit's timestamp in a FIFO queue. Because calls arrive in chronological order, older hits are always at the front. On getHits(t), pop while the front is <= t - 300; the remaining count is the number of hits in the last 5 minutes.

hit(t): queue.append(t)
getHits(t): pop while front <= t-300; return len(queue)

Worked example

hits at 1,2,3, then getHits(4)=3; hit at 300; getHits(300)=4; getHits(301) drops the hit at 1 → 3.

Complexity

• Time: hit O(1); getHits amortized O(1).
• Space: O(number of recent hits).

import java.util.ArrayDeque;
import java.util.Queue;

class HitCounter {
    private Queue<Integer> hits = new ArrayDeque<>();

    public HitCounter() {
    }

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

    public int getHits(int timestamp) {
        while (!hits.isEmpty() && hits.peek() <= timestamp - 300) {
            hits.poll();
        }
        return hits.size();
    }
}