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:

timestamp: int
message: str

Return:

True

if the message should be printed.

Return:

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

The timestamp is measured in seconds.

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

Example function shape:

class Logger:

    def __init__(self):
        ...

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

Examples

Example calls:

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:

True
True
False
False
False
True

Step by step:

First Thought: Store All Printed Events

One direct design is to store every printed message event:

[(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:

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:

message -> next_allowed_timestamp

When a message arrives at timestamp t:

If we print the message at timestamp t, update:

next_allowed_timestamp = t + 10

This makes the check simple.

Algorithm

Maintain:

self.next_allowed

where:

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:

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.

The hash map stores one entry per distinct message.

Implementation

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:

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:

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:

if timestamp >= self.next_allowed[message]:

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

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

Otherwise, block it:

return False

Alternative Implementation: Store Last Printed Timestamp

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

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:

Can I print at this timestamp?

The last_printed version makes the decision read as:

Has enough time passed since the last print?

Testing

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: