Design Hit Counter

The most direct reading of the problem: append each timestamp to a list, and on every query walk the whole list and count the entries that pass the window test. It is correct and trivial, but getHits pays for every hit ever recorded, including the millions that have long since aged out.

class HitCounter:
    def __init__(self):
        self.timestamps: list[int] = []

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

    def getHits(self, timestamp: int) -> int:
        # A hit counts iff timestamp - ts < 300, i.e. ts > timestamp - 300.
        return sum(1 for ts in self.timestamps if timestamp - ts < 300)

Why it is linear: hit is a single append, so O(1). getHits inspects all n stored timestamps → O(n) time, and the list keeps every hit forever → O(n) space. With 2 * 10^9 possible timestamps and no upper bound on hit volume, this is the design the two improvements below replace.

The brute force rescans hits that can never count again. Since timestamps are non-decreasing, hits expire in arrival order, so a double-ended queue is the natural home for them: the front is the oldest live hit, the back is the newest. Before answering a query, pop the front while it is at or before timestamp - 300 — those hits are dead for this call and for every later call, because future queries are even larger. Whatever remains is exactly the window.

from collections import deque

class HitCounter:
    def __init__(self):
        self.hits: deque[int] = deque()

    def hit(self, timestamp: int) -> None:
        self.hits.append(timestamp)
        # Nothing at or before timestamp - 300 can ever count again.
        while self.hits and self.hits[0] <= timestamp - 300:
            self.hits.popleft()

    def getHits(self, timestamp: int) -> int:
        while self.hits and self.hits[0] <= timestamp - 300:
            self.hits.popleft()
        return len(self.hits)

Why it is amortized constant: every timestamp is appended once and popped once, so the total work across all calls is O(number of hits), i.e. O(1) amortized per call — a query that pops 500 stale hits is paid for by the 500 calls that pushed them. The catch is space: if one second receives a huge burst, the deque still holds one entry per hit, not per second, so memory grows with the number of hits in the window and the follow-up question breaks it. (A sorted list plus bisect_left(hits, timestamp - 299) is the same idea with O(log n) queries and the same O(n) footprint.)

The deque stores an entry per hit, but hits only ever need to be counted, never inspected — so there is no reason to keep them individually. Instead, give the window one slot per second: a circular array of length 300, where second t always maps to slot t % 300. Two parallel arrays describe a slot: times[i] is the second that slot currently represents, and hits[i] is how many hits landed in that second. A hit either increments the slot if it already represents the same second, or overwrites it. A query sums the slots whose stored second is still inside the window.

class HitCounter:
    WINDOW = 300

    def __init__(self):
        # Both arrays are indexed by timestamp % 300.
        self.times = [0] * self.WINDOW   # the second slot i last stored
        self.hits = [0] * self.WINDOW    # hits recorded in that second

    def hit(self, timestamp: int) -> None:
        i = timestamp % self.WINDOW
        if self.times[i] == timestamp:
            self.hits[i] += 1            # same second: aggregate
        else:
            self.times[i] = timestamp    # a new second reuses the slot
            self.hits[i] = 1

    def getHits(self, timestamp: int) -> int:
        total = 0
        for i in range(self.WINDOW):
            if timestamp - self.times[i] < self.WINDOW:
                total += self.hits[i]
        return total

Why overwriting is safe: two different seconds that share a slot differ by a multiple of 300. So when t is written into a slot that held t - 300 (or older), that old second already fails the test timestamp - times[i] < 300 for every future timestamp, meaning its hits could never be counted again — the slot is free to reuse. This is also why stale data can never leak into an answer: a slot either represents a second inside the window, or it represents an older second whose count is correctly ignored. And because all hits in one second share the single counter hits[i], a burst of a million hits in the same second costs one integer, which is precisely what the follow-up asks for.

Why it is constant: hit does one modulo and one array write → O(1). getHits scans a fixed 300 slots regardless of how much traffic arrived → O(1) time (the 300 is a constant, not a function of the input). Both arrays are length 300 → O(1) space. This is the standard answer to the problem.

Watch how the ring wraps and how the window test retires a slot — first the statement example, hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301), where the outputs must be 3, 4, 3:

Then a second trace that exercises the two cases the example skips — two hits in the same second, and a slot reused by a later second whose older occupant has already expired:

Both traces match the reference implementation exactly. The first ends with outputs 3, 4, 3; the second with 3, 2, and shows that hits[i] can hold any count while times[i] keeps the slot honest about which second it belongs to.