# LeetCode 933: Number of Recent Calls

## Problem Restatement

We need to implement a class called `RecentCounter`.

It supports one main operation:

```python
ping(t)
```

Each call records a request at time `t`, measured in milliseconds.

After recording the request, `ping(t)` must return how many requests happened in the time range:

```text
[t - 3000, t]
```

The current request is included.

The problem guarantees that every new `t` is strictly larger than the previous one. The official statement defines `RecentCounter()`, `ping(t)`, and the inclusive recent window `[t - 3000, t]`.

## Input and Output

| Item | Meaning |
|---|---|
| Constructor | Initializes an empty counter |
| `ping(t)` input | A request time in milliseconds |
| `ping(t)` output | Number of requests in `[t - 3000, t]` |
| Important guarantee | Each `t` is strictly increasing |

Class shape:

```python
class RecentCounter:

    def __init__(self):
        ...

    def ping(self, t: int) -> int:
        ...
```

## Examples

Example:

```text
Input:
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

Output:
[null, 1, 2, 3, 3]
```

Step by step:

```python
ping(1)
```

Valid range:

```text
[-2999, 1]
```

Only request `1` is inside.

Return:

```python
1
```

Next:

```python
ping(100)
```

Valid range:

```text
[-2900, 100]
```

Requests `1` and `100` are inside.

Return:

```python
2
```

Next:

```python
ping(3001)
```

Valid range:

```text
[1, 3001]
```

Requests `1`, `100`, and `3001` are inside.

Return:

```python
3
```

Next:

```python
ping(3002)
```

Valid range:

```text
[2, 3002]
```

Request `1` is now too old.

Requests `100`, `3001`, and `3002` are inside.

Return:

```python
3
```

## First Thought: Store All Requests and Count Each Time

One simple solution is to store every request time in a list.

For each `ping(t)`, scan the whole list and count how many values are at least `t - 3000`.

That works, but each call may scan many old requests that can never be useful again.

Because `t` always increases, once a request is older than `t - 3000`, it will also be too old for all future calls.

So we should remove old requests instead of keeping them forever.

## Key Insight

This is a sliding window over time.

For each new time `t`, the valid window is:

```text
[t - 3000, t]
```

Since calls arrive in increasing order, request times are naturally sorted.

The oldest requests are always at the front.

So we can use a queue:

1. Push the new request time to the back.
2. Remove request times from the front while they are too old.
3. The queue length is the answer.

A request is too old when:

```python
queue[0] < t - 3000
```

The range is inclusive, so a request at exactly `t - 3000` must stay.

## Algorithm

Initialize an empty queue:

```python
self.q = deque()
```

For each `ping(t)`:

1. Append `t`.
2. Compute the oldest valid time:

```python
left = t - 3000
```

3. While the queue front is smaller than `left`, remove it.
4. Return the queue length.

## Walkthrough

For calls:

```python
ping(1), ping(100), ping(3001), ping(3002)
```

| Call | Queue after append | Remove old values | Queue after cleanup | Return |
|---|---|---|---|---:|
| `ping(1)` | `[1]` | none | `[1]` | 1 |
| `ping(100)` | `[1, 100]` | none | `[1, 100]` | 2 |
| `ping(3001)` | `[1, 100, 3001]` | none, because `1` is valid | `[1, 100, 3001]` | 3 |
| `ping(3002)` | `[1, 100, 3001, 3002]` | remove `1` | `[100, 3001, 3002]` | 3 |

The answer sequence is:

```python
[1, 2, 3, 3]
```

## Correctness

The queue stores request times that have been recorded and have not yet become too old.

When `ping(t)` is called, the algorithm first appends `t`, so the current request is included.

Then it removes every request time smaller than `t - 3000`. These requests are outside the required range `[t - 3000, t]`, so they must not be counted.

It keeps every request time greater than or equal to `t - 3000`. Since all request times are at most `t` at that moment, every remaining request lies inside `[t - 3000, t]`.

Because `t` values are strictly increasing, the queue is sorted by time. Therefore, all too-old requests appear at the front, and removing from the front removes exactly the expired requests.

After cleanup, the queue contains exactly the recent requests in the required time window. Returning its length gives the correct count.

## Complexity

Let `m` be the number of calls to `ping`.

| Metric | Value | Why |
|---|---|---|
| Time per call | Amortized `O(1)` | Each request is appended once and removed once |
| Space | `O(m)` worst case | The queue stores requests still inside the active window |

## Implementation

```python
from collections import deque

class RecentCounter:

    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        self.q.append(t)

        left = t - 3000

        while self.q[0] < left:
            self.q.popleft()

        return len(self.q)
```

## Code Explanation

We keep a queue of active request times:

```python
self.q = deque()
```

Each new request is appended:

```python
self.q.append(t)
```

The oldest valid timestamp is:

```python
left = t - 3000
```

Then we remove expired requests:

```python
while self.q[0] < left:
    self.q.popleft()
```

We use `< left`, not `<= left`, because the range includes `t - 3000`.

Finally, the number of recent requests is exactly the queue length:

```python
return len(self.q)
```

## Testing

```python
def run_tests():
    rc = RecentCounter()

    assert rc.ping(1) == 1
    assert rc.ping(100) == 2
    assert rc.ping(3001) == 3
    assert rc.ping(3002) == 3

    rc = RecentCounter()
    assert rc.ping(3000) == 1
    assert rc.ping(6000) == 2
    assert rc.ping(6001) == 2

    rc = RecentCounter()
    assert rc.ping(1) == 1
    assert rc.ping(3002) == 1
    assert rc.ping(6003) == 1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `1, 100, 3001, 3002` | Official example |
| `3000, 6000` | Boundary value exactly `t - 3000` stays |
| `6001` after `3000` | Value older than window is removed |
| Large gaps | Queue can shrink to one request |