> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Design Hit Counter Python Solution with Tests

> Tested Python solution for LeetCode 362 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 362, Medium. Topics: Design, Queue, Array, Binary Search, Data Stream. [View on LeetCode](https://leetcode.com/problems/design-hit-counter/description/).

Generate this problem as a practice environment: tested reference solution, 13 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 362   # by problem number
lcpy gen -s design_hit_counter   # by problem name
```

## Problem

Design a hit counter which counts the number of hits received in the past `5` minutes (i.e., the past `300` seconds).

Your system should accept a `timestamp` parameter (**in seconds** granularity), and you may assume that calls are being made to the system in chronological order (i.e., `timestamp` is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the `HitCounter` class:

* `HitCounter()` Initializes the object of the hit counter system.
* `void hit(int timestamp)` Records a hit that happened at `timestamp` (**in seconds**). Several hits may happen at the same `timestamp`.
* `int getHits(int timestamp)` Returns the number of hits in the past 5 minutes from `timestamp` (i.e., the past `300` seconds).

### Examples

```
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
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.
```

### Constraints

* `1 <= timestamp <= 2 * 10^9`
* All the calls are being made to the system in chronological order (i.e., `timestamp` is monotonically increasing).
* At most `300` calls will be made to `hit` and `getHits`.

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_hit_counter/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_hit_counter/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class HitCounter:
    # Time: O(1) amortized per hit / get_hits
    # Space: O(n) where n is number of distinct timestamps in the 300s window
    def __init__(self) -> None:
        # Pairs of [timestamp, count] coalesce same-second hits so the counter
        # scales even when hits per second are huge (follow-up).
        self.deque: deque[list[int]] = deque()
        self.total = 0

    # Time: O(1)
    # Space: O(1)
    def hit(self, timestamp: int) -> None:
        if self.deque and self.deque[-1][0] == timestamp:
            self.deque[-1][1] += 1
        else:
            self.deque.append([timestamp, 1])
        self.total += 1

    # Time: O(1) amortized
    # Space: O(1)
    def get_hits(self, timestamp: int) -> int:
        # A hit at time t stays valid for 300 seconds, i.e. while
        # t > timestamp - 300. Evict entries that have expired.
        while self.deque and self.deque[0][0] <= timestamp - 300:
            _, count = self.deque.popleft()
            self.total -= count
        return self.total
```

## Complexity

| Time                               | Space                                                            |
| ---------------------------------- | ---------------------------------------------------------------- |
| O(1) amortized per hit / get\_hits | O(n) where n is number of distinct timestamps in the 300s window |

## Tags

[Grind](/catalog/grind), [NeetCode All](/catalog/neetcode).