# LeetCode 359: Logger Rate Limiter

## Problem Restatement

We need to design a logger system.

The logger receives messages with timestamps.

Each message should be printed only if the same message was not printed in the last `10` seconds.

Given:

```python
timestamp: int
message: str
```

Return:

```python
True
```

if the message should be printed.

Return:

```python
False
```

if the message should be blocked.

A message printed at timestamp `t` prevents the same message from being printed again until timestamp `t + 10`. Messages arrive in chronological order, and several messages may arrive at the same timestamp.

## Input and Output

| Method | Meaning |
|---|---|
| `Logger()` | Initializes the logger |
| `shouldPrintMessage(timestamp, message)` | Returns whether this message should be printed |

The timestamp is measured in seconds.

The same message can be printed again when at least `10` seconds have passed.

Example function shape:

```python
class Logger:

    def __init__(self):
        ...

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        ...
```

## Examples

Example calls:

```python
logger = Logger()

logger.shouldPrintMessage(1, "foo")
logger.shouldPrintMessage(2, "bar")
logger.shouldPrintMessage(3, "foo")
logger.shouldPrintMessage(8, "bar")
logger.shouldPrintMessage(10, "foo")
logger.shouldPrintMessage(11, "foo")
```

Expected output:

```python
True
True
False
False
False
True
```

Step by step:

| Call | Result | Why |
|---|---:|---|
| `(1, "foo")` | `True` | `"foo"` has never been printed |
| `(2, "bar")` | `True` | `"bar"` has never been printed |
| `(3, "foo")` | `False` | `"foo"` was printed at `1`, and `3 - 1 < 10` |
| `(8, "bar")` | `False` | `"bar"` was printed at `2`, and `8 - 2 < 10` |
| `(10, "foo")` | `False` | `"foo"` was printed at `1`, and `10 - 1 < 10` |
| `(11, "foo")` | `True` | `"foo"` was printed at `1`, and `11 - 1 >= 10` |

## First Thought: Store All Printed Events

One direct design is to store every printed message event:

```python
[(timestamp, message), ...]
```

Then for each new message, scan backward to find whether the same message was printed in the last `10` seconds.

This works, but it does too much work.

If many messages have been printed, each call may need to scan many old events.

We only need one fact per message:

```text
When can this message be printed again?
```

## Key Insight

For each message, store the next timestamp when it is allowed to print again.

Use a hash map:

```python
message -> next_allowed_timestamp
```

When a message arrives at timestamp `t`:

| Condition | Meaning |
|---|---|
| message unseen | Print it |
| `t >= next_allowed_timestamp` | Print it |
| `t < next_allowed_timestamp` | Block it |

If we print the message at timestamp `t`, update:

```python
next_allowed_timestamp = t + 10
```

This makes the check simple.

## Algorithm

Maintain:

```python
self.next_allowed
```

where:

```text
self.next_allowed[message] = earliest timestamp when message can print again
```

For `shouldPrintMessage(timestamp, message)`:

1. If `message` is not in the map, print it.
2. If `timestamp >= self.next_allowed[message]`, print it.
3. Otherwise, block it.
4. When printing, set:

```python
self.next_allowed[message] = timestamp + 10
```

5. Return `True` for printed messages and `False` for blocked messages.

## Correctness

For every message, the map stores the earliest timestamp at which that message may be printed again.

When a message has never been printed, no rate limit applies, so the algorithm returns `True`.

When the current timestamp is smaller than the stored allowed timestamp, fewer than `10` seconds have passed since the last printed occurrence of that message. The logger must block it, so returning `False` is correct.

When the current timestamp is greater than or equal to the stored allowed timestamp, at least `10` seconds have passed since the last printed occurrence. The logger may print it, so returning `True` is correct.

After every printed message, the algorithm updates the next allowed timestamp to `timestamp + 10`. That exactly matches the rule that the same message cannot be printed again during the next `10` seconds.

Therefore, every call returns the correct decision.

## Complexity

Let `m` be the number of distinct messages seen so far.

| Operation | Time | Space |
|---|---:|---:|
| `Logger()` | `O(1)` | `O(1)` |
| `shouldPrintMessage` | `O(1)` average | `O(m)` total |

The hash map stores one entry per distinct message.

## Implementation

```python
class Logger:

    def __init__(self):
        self.next_allowed = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.next_allowed:
            self.next_allowed[message] = timestamp + 10
            return True

        if timestamp >= self.next_allowed[message]:
            self.next_allowed[message] = timestamp + 10
            return True

        return False
```

## Code Explanation

The constructor creates an empty hash map:

```python
self.next_allowed = {}
```

The key is the message string.

The value is the earliest timestamp when that same message can be printed again.

If a message has never appeared before, it can be printed immediately:

```python
if message not in self.next_allowed:
    self.next_allowed[message] = timestamp + 10
    return True
```

If the message has appeared before, compare the current timestamp with its next allowed timestamp:

```python
if timestamp >= self.next_allowed[message]:
```

If the current timestamp is large enough, print it and refresh the cooldown:

```python
self.next_allowed[message] = timestamp + 10
return True
```

Otherwise, block it:

```python
return False
```

## Alternative Implementation: Store Last Printed Timestamp

We can also store the last printed timestamp instead of the next allowed timestamp.

```python
class Logger:

    def __init__(self):
        self.last_printed = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.last_printed:
            self.last_printed[message] = timestamp
            return True

        if timestamp - self.last_printed[message] >= 10:
            self.last_printed[message] = timestamp
            return True

        return False
```

Both versions are correct.

The `next_allowed` version makes the decision read as:

```text
Can I print at this timestamp?
```

The `last_printed` version makes the decision read as:

```text
Has enough time passed since the last print?
```

## Testing

```python
def run_tests():
    logger = Logger()

    assert logger.shouldPrintMessage(1, "foo") is True
    assert logger.shouldPrintMessage(2, "bar") is True
    assert logger.shouldPrintMessage(3, "foo") is False
    assert logger.shouldPrintMessage(8, "bar") is False
    assert logger.shouldPrintMessage(10, "foo") is False
    assert logger.shouldPrintMessage(11, "foo") is True

    logger = Logger()

    assert logger.shouldPrintMessage(1, "same") is True
    assert logger.shouldPrintMessage(1, "same") is False
    assert logger.shouldPrintMessage(11, "same") is True

    logger = Logger()

    assert logger.shouldPrintMessage(5, "a") is True
    assert logger.shouldPrintMessage(6, "b") is True
    assert logger.shouldPrintMessage(15, "a") is True
    assert logger.shouldPrintMessage(15, "b") is False
    assert logger.shouldPrintMessage(16, "b") is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard sequence | Checks normal rate limiting |
| Same timestamp duplicate | Confirms repeated message at same second is blocked |
| Boundary at exactly `10` seconds | Confirms `timestamp >= previous + 10` is allowed |
| Different messages | Confirms each message has its own cooldown |