LeetCode 359 - Logger Rate Limiter

The problem asks us to design a logging system that controls how frequently identical messages can be printed. Each message is associated with a timestamp, and the same message is only allowed to be printed once every 10 seconds.

leetcodeeasyhash-tabledesigndata-stream

LeetCode Problem 359

Difficulty: 🟢 Easy
Topics: Hash Table, Design, Data Stream

Solution

Problem Understanding

The problem asks us to design a logging system that controls how frequently identical messages can be printed. Each message is associated with a timestamp, and the same message is only allowed to be printed once every 10 seconds.

More specifically, when a message is printed at timestamp t, the next time the exact same message can be printed is at timestamp t + 10. Any attempt to print that same message before then must return false.

The method shouldPrintMessage(timestamp, message) determines whether the message should be printed at the current timestamp. If the message is allowed, the method returns true and updates the internal state so future calls know when the message becomes eligible again. Otherwise, it returns false.

The input stream is guaranteed to arrive in chronological order, meaning timestamps never decrease. Multiple messages may arrive at the same timestamp. This guarantee is important because it simplifies the logic and removes the need to handle out-of-order events.

The constraints are relatively small:

  • At most 10^4 calls will be made
  • Message length is at most 30 characters
  • Timestamps can be as large as 10^9

Although 10^4 operations is not extremely large, we still want an efficient design because the problem is fundamentally about implementing a real-time rate limiter.

Several edge cases are important:

  • The same message appearing repeatedly within 10 seconds
  • Messages arriving exactly at the boundary, such as timestamp 11 after being printed at timestamp 1
  • Different messages arriving at the same timestamp
  • Large timestamps that could expose incorrect arithmetic logic
  • First-time messages that have never been seen before

The problem guarantees chronological ordering, so we never need to reconsider earlier timestamps or reorder data.

Approaches

Brute Force Approach

A brute-force solution would store every successful print timestamp for every message. Whenever a new request arrives, we would scan the history of that message to determine whether at least 10 seconds have passed since the most recent successful print.

For example, if "foo" was previously printed at timestamps [1, 15, 30], and a new request comes at timestamp 35, we would check the latest successful timestamp and determine whether 35 - 30 >= 10.

A naive implementation might even scan all previous timestamps for the message every time a new request arrives. This works correctly because it explicitly checks the history of each message before deciding whether printing is allowed.

However, this approach is inefficient because repeated scanning introduces unnecessary overhead. As the number of calls grows, the repeated traversal becomes more expensive.

Optimal Approach

The key observation is that we only care about the most recent successful print time for each message.

If a message was last printed at timestamp t, then the next valid timestamp is t + 10. Earlier timestamps are irrelevant because only the latest successful print determines eligibility.

This means we can maintain a hash map:

  • Key = message string
  • Value = most recent successful print timestamp

For every incoming request:

  • If the message has never been seen before, print it
  • Otherwise, check whether timestamp - lastPrinted >= 10
  • If true, update the timestamp and allow printing
  • Otherwise, reject the request

A hash map provides average O(1) lookup and update time, making the solution highly efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per call O(n) Stores full message history and may scan previous timestamps
Optimal O(1) per call O(n) Stores only the latest successful timestamp for each message

Algorithm Walkthrough

  1. Initialize a hash map called last_printed.

The keys will be message strings, and the values will be the most recent timestamp at which that message was successfully printed. 2. When shouldPrintMessage(timestamp, message) is called, first check whether the message exists in the hash map.

If the message does not exist, it means this is the first time we have seen it, so it should always be printed. 3. If the message exists, retrieve its most recent successful print timestamp.

We compare the current timestamp against that stored value. 4. Compute the time difference.

If timestamp - last_printed[message] >= 10, enough time has passed, so the message is allowed to print again. 5. If the message is allowed, update the hash map.

Store the current timestamp as the new most recent successful print time. 6. Return the result.

Return true when the message is allowed and false otherwise.

Why it works

The algorithm works because the only information needed to determine whether a message can be printed is the timestamp of its most recent successful print.

If a message was last printed at timestamp t, then every timestamp before t + 10 must be rejected, and every timestamp at or after t + 10 must be accepted. Earlier history does not affect future decisions.

By always maintaining the latest successful timestamp for each message, the algorithm preserves exactly the information required for correctness.

Python Solution

class Logger:

    def __init__(self):
        self.last_printed: dict[str, int] = {}

    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

# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp, message)

The implementation uses a dictionary named last_printed to track the most recent successful print timestamp for every message.

Inside __init__, the dictionary starts empty because no messages have been processed yet.

In shouldPrintMessage, the first condition checks whether the message has ever appeared before. If not, the message is immediately allowed, and its timestamp is recorded.

If the message already exists, the code calculates the difference between the current timestamp and the last successful print timestamp. When the difference is at least 10 seconds, the message becomes eligible again, so the timestamp is updated and True is returned.

If fewer than 10 seconds have passed, the method returns False without modifying the stored timestamp.

The implementation directly follows the algorithm described earlier and achieves constant-time average performance using hash map operations.

Go Solution

type Logger struct {
    lastPrinted map[string]int
}

func Constructor() Logger {
    return Logger{
        lastPrinted: make(map[string]int),
    }
}

func (this *Logger) ShouldPrintMessage(timestamp int, message string) bool {
    lastTime, exists := this.lastPrinted[message]

    if !exists {
        this.lastPrinted[message] = timestamp
        return true
    }

    if timestamp-lastTime >= 10 {
        this.lastPrinted[message] = timestamp
        return true
    }

    return false
}

/**
 * Your Logger object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.ShouldPrintMessage(timestamp,message);
 */

The Go implementation mirrors the Python solution closely.

Instead of a Python dictionary, Go uses map[string]int. The Constructor function initializes the map using make.

Go maps return two values during lookup:

lastTime, exists := this.lastPrinted[message]

The boolean exists indicates whether the key is present. This cleanly distinguishes first-time messages from previously stored ones.

Go integers are sufficient because timestamps are bounded by 10^9, which comfortably fits within Go's integer range.

Worked Examples

Example 1

Input:

["Logger",
 "shouldPrintMessage",
 "shouldPrintMessage",
 "shouldPrintMessage",
 "shouldPrintMessage",
 "shouldPrintMessage",
 "shouldPrintMessage"]

Operations:

[[], [1, "foo"], [2, "bar"], [3, "foo"],
 [8, "bar"], [10, "foo"], [11, "foo"]]
Step Timestamp Message Previous State Decision New State
1 1 foo {} True {"foo": 1}
2 2 bar {"foo": 1} True {"foo": 1, "bar": 2}
3 3 foo {"foo": 1, "bar": 2} False because 3 - 1 < 10 unchanged
4 8 bar {"foo": 1, "bar": 2} False because 8 - 2 < 10 unchanged
5 10 foo {"foo": 1, "bar": 2} False because 10 - 1 < 10 unchanged
6 11 foo {"foo": 1, "bar": 2} True because 11 - 1 >= 10 {"foo": 11, "bar": 2}

Final output:

[null, true, true, false, false, false, true]

Complexity Analysis

Measure Complexity Explanation
Time O(1) average per call Hash map lookup and update are constant time on average
Space O(n) Stores one timestamp per unique message

The time complexity is constant on average because hash map operations, including insertion and lookup, are typically O(1).

The space complexity depends on the number of distinct messages encountered. In the worst case, every request contains a unique message, so the hash map stores n entries.

Test Cases

# Provided example
logger = Logger()
assert logger.shouldPrintMessage(1, "foo") is True   # first appearance
assert logger.shouldPrintMessage(2, "bar") is True   # different message
assert logger.shouldPrintMessage(3, "foo") is False  # blocked within 10 seconds
assert logger.shouldPrintMessage(8, "bar") is False  # blocked within 10 seconds
assert logger.shouldPrintMessage(10, "foo") is False # still blocked
assert logger.shouldPrintMessage(11, "foo") is True  # exactly 10 seconds later

# Single repeated message
logger = Logger()
assert logger.shouldPrintMessage(0, "a") is True
assert logger.shouldPrintMessage(1, "a") is False
assert logger.shouldPrintMessage(9, "a") is False
assert logger.shouldPrintMessage(10, "a") is True

# Multiple messages at same timestamp
logger = Logger()
assert logger.shouldPrintMessage(5, "x") is True
assert logger.shouldPrintMessage(5, "y") is True
assert logger.shouldPrintMessage(5, "x") is False

# Large timestamps
logger = Logger()
assert logger.shouldPrintMessage(1000000000, "big") is True
assert logger.shouldPrintMessage(1000000005, "big") is False
assert logger.shouldPrintMessage(1000000010, "big") is True

# Different messages do not interfere
logger = Logger()
assert logger.shouldPrintMessage(1, "foo") is True
assert logger.shouldPrintMessage(2, "bar") is True
assert logger.shouldPrintMessage(3, "baz") is True

# Exact boundary condition
logger = Logger()
assert logger.shouldPrintMessage(15, "test") is True
assert logger.shouldPrintMessage(25, "test") is True  # exactly 10 seconds later

# Consecutive valid prints
logger = Logger()
assert logger.shouldPrintMessage(1, "msg") is True
assert logger.shouldPrintMessage(11, "msg") is True
assert logger.shouldPrintMessage(21, "msg") is True
Test Why
Provided example Validates core functionality
Single repeated message Ensures repeated blocking works
Multiple messages at same timestamp Confirms independent tracking
Large timestamps Verifies arithmetic correctness
Different messages do not interfere Ensures separate hash map entries
Exact boundary condition Confirms >= 10 logic
Consecutive valid prints Ensures timestamps update correctly

Edge Cases

Messages Printed Exactly 10 Seconds Later

A very common bug is incorrectly using > instead of >= when checking eligibility.

For example, if "foo" is printed at timestamp 1, then timestamp 11 must be allowed because 11 - 1 = 10.

The implementation correctly handles this using:

timestamp - self.last_printed[message] >= 10

This ensures boundary values behave exactly as required.

Multiple Different Messages at the Same Timestamp

Several messages may arrive at the same timestamp, and different messages should not interfere with one another.

For example:

(5, "foo")
(5, "bar")

Both should be allowed because they are distinct messages.

The hash map stores timestamps independently for each message key, so operations on one message never affect another.

Repeated Blocked Requests

Another subtle issue occurs when blocked requests accidentally update the stored timestamp.

For example:

(1, "foo")  -> allowed
(5, "foo")  -> blocked
(11, "foo") -> should still be allowed

If the blocked request at timestamp 5 incorrectly updated the stored timestamp, then timestamp 11 would wrongly fail.

The implementation avoids this by only updating the timestamp when the message is successfully printed. Blocked requests leave the stored value unchanged.