LeetCode 359: Logger Rate Limiter Solution in Python – A Step-by-Step Guide

What Is LeetCode 359: Logger Rate Limiter?

LeetCode 359: Logger Rate Limiter asks you to design a Logger class that tracks messages and their timestamps, allowing a message to be printed only if at least 10 seconds have passed since its last appearance. It’s a simple yet practical problem of rate limiting—perfect for learning time-based data management!

Problem Statement

• Class: Logger
• Methods:
• __init__(): Initialize the logger.
• shouldPrintMessage(timestamp, message): Return True if the message can be printed at the given timestamp, False otherwise.
• Rules:
• A message can be printed if no identical message was printed in the last 10 seconds (inclusive).
• Timestamps are in seconds, non-decreasing.

Constraints

• 0 <= timestamp <= 10⁹
• 1 <= message.length <= 30
• At most 10⁴ calls to shouldPrintMessage.
• Messages contain lowercase English letters and spaces.

Examples

• Input: ["Logger","shouldPrintMessage","shouldPrintMessage","shouldPrintMessage"], [[],[1,"foo"],[2,"bar"],[3,"foo"]]
• Output: [null,true,true,false]
• 1s: "foo" → True (new).
• 2s: "bar" → True (new).
• 3s: "foo" → False (only 2s since last "foo").
• Input: ["Logger","shouldPrintMessage","shouldPrintMessage"], [[],[1,"foo"],[11,"foo"]]
• Output: [null,true,true]
• 1s: "foo" → True.
• 11s: "foo" → True (10s passed).

These show the 10-second rule—let’s solve it!

Understanding the Problem: Rate Limiting Messages

To tackle LeetCode 359 in Python, we need a class that: 1. Tracks each message and its last timestamp. 2. Checks if 10 seconds have elapsed since the last occurrence. 3. Updates the timestamp if printing is allowed.

A brute-force approach might store all timestamps and scan them, but that’s inefficient. Instead, we’ll use:

• Best Solution: Hash map—O(1) time, O(m) space—fast and simple.
• Alternative Solution: Queue with timestamps—O(n) time, O(n) space—intuitive but slower.

Let’s log with the best solution!

Best Solution: Hash Map

Why This Is the Best Solution

The hash map approach runs in O(1) time per call by storing each message with its most recent timestamp in a dictionary. Checking and updating take constant time, making it the most efficient solution—ideal for real-time rate limiting!

How It Works

Think of it like a message logbook:

• Setup: Use a dictionary where keys are messages and values are the last timestamp they were printed.
• Check: For a new timestamp and message:
• If message isn’t in the map or timestamp ≥ last_time + 10, print and update.
• Otherwise, skip (False).
• Result: True if printed, False if blocked.

It’s like checking a timestamp sticker on each message!

Step-by-Step Example

For calls: shouldPrintMessage(1, "foo"), shouldPrintMessage(2, "bar"), shouldPrintMessage(3, "foo"), shouldPrintMessage(11, "foo"):

• Init: msg_time = {}.
• 1s, "foo":
• Not in map, print, msg_time = {"foo": 1}, return True.
• 2s, "bar":
• Not in map, print, msg_time = {"foo": 1, "bar": 2}, return True.
• 3s, "foo":
• In map, 3 < 1 + 10 (11), skip, return False.
• 11s, "foo":
• In map, 11 ≥ 1 + 10, print, msg_time = {"foo": 11, "bar": 2}, return True.

Output: [true, true, false, true].

Let’s code it with a clear breakdown!

Code with Explanation

Here’s the Python code using a hash map:

Copy codeclass Logger:
    def __init__(self):
        # Initialize a dictionary to store message -> timestamp
        self.msg_time = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # Check if message can be printed
        if message not in self.msg_time or timestamp >= self.msg_time[message] + 10:
            # Update timestamp and return True
            self.msg_time[message] = timestamp
            return True
        # Message is too recent, return False
        return False

Explanation

• Lines 3-4: __init__: Create an empty dictionary msg_time to map messages to their last timestamps.
• Lines 6-12: shouldPrintMessage:
• Line 7: Check two conditions:
• message not in self.msg_time: First occurrence, can print.
• timestamp >= self.msg_time[message] + 10: Enough time (10s) has passed.
• Lines 9-10: If True, update the timestamp for this message and return True.
• Line 12: If False, return False (message is too recent).

• Time Complexity: O(1)—dictionary lookups and updates are constant time.
• Space Complexity: O(m)—where m is the number of unique messages (bounded by calls, up to 10⁴).

This is like a quick timestamp check—simple and fast!

Alternative Solution: Queue with Timestamps

Why an Alternative Approach?

The queue-based solution uses a deque to store all message-timestamp pairs, removing old entries as time progresses. It’s O(n) per call but shows how to track history explicitly—great for learning or when memory is less critical!

How It Works

• Setup: Use a deque to store (timestamp, message) pairs.
• Check:
• Remove pairs older than 10 seconds.
• Check if the message exists in the remaining queue.
• If not, add it and print.
• Result: True if printed, False if blocked.

It’s like a rolling log of recent messages!

Step-by-Step Example

For calls: shouldPrintMessage(1, "foo"), shouldPrintMessage(2, "bar"), shouldPrintMessage(3, "foo"), shouldPrintMessage(11, "foo"):

• Init: queue = deque().
• 1s, "foo":
• Queue empty, add (1, "foo"), queue = [(1, "foo")], return True.
• 2s, "bar":
• All < 10s old, "bar" not in queue, add (2, "bar"), queue = [(1, "foo"), (2, "bar")], return True.
• 3s, "foo":
• All < 10s old, "foo" in queue at 1s, return False.
• 11s, "foo":
• Remove (1, "foo") (11-1 ≥ 10), queue = [(2, "bar")], "foo" not in queue, add (11, "foo"), queue = [(2, "bar"), (11, "foo")], return True.

Output: [true, true, false, true].

Code with Explanation

Copy codefrom collections import deque

class Logger:
    def __init__(self):
        # Initialize a deque to store (timestamp, message) pairs
        self.queue = deque()

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # Remove messages older than 10 seconds
        while self.queue and timestamp >= self.queue[0][0] + 10:
            self.queue.popleft()

        # Check if message exists in remaining queue
        for t, msg in self.queue:
            if msg == message:
                return False

        # Message can be printed, add to queue
        self.queue.append((timestamp, message))
        return True

Explanation

• Lines 3-5: __init__: Create an empty deque to store (timestamp, message) pairs.
• Lines 7-17: shouldPrintMessage:
• Lines 9-10: While the oldest entry is ≥ 10s before the current timestamp, remove it.
• Lines 12-14: Scan queue for the message; if found, return False.
• Lines 16-17: If not found, add the new (timestamp, message) pair and return True.

• Time Complexity: O(n)—where n is the number of messages in the queue (up to 10⁴ calls).
• Space Complexity: O(n)—queue stores all messages within 10s.

It’s like a sliding window of recent logs!

Comparing the Two Solutions

• Hash Map (Best):
• Time: O(1)—constant lookups.
• Space: O(m)—unique messages.
• Pros: Fast, memory-efficient.
• Cons: Less history visibility.
• Queue with Timestamps (Alternative):
• Time: O(n)—linear scan and removal.
• Space: O(n)—all recent messages.
• Pros: Explicit time tracking.
• Cons: Slower, more memory.

Hash map wins for speed and simplicity!

Additional Examples and Edge Cases

• 1,"foo"; 1,"foo": [True, False] (same timestamp).
• 0,"a"; 10,"a": [True, True] (exactly 10s).
• Empty calls: Works (empty map/queue).

Both solutions handle these well.

Complexity Breakdown

• Hash Map:
• Time: O(1).
• Space: O(m).
• Queue:
• Time: O(n).
• Space: O(n).

Hash map excels for performance.

Key Takeaways

• Hash Map: Quick checks—perfect for rate limiting!
• Queue: Track history—great for learning!
• Time: Simple rules, big impact.
• Python Tip: Dicts and deques shine—see [Python Basics](/python/basics).

Final Thoughts: Limit That Log

LeetCode 359: Logger Rate Limiter in Python is a time-based challenge. The hash map solution is the efficiency champ, while the queue builds intuition. Want more? Try LeetCode 346: Moving Average or LeetCode 362: Design Hit Counter. Ready to log? Visit Solve LeetCode 359 on LeetCode and control that flow today!