Leetcode - Logger Rate Limiter Solution

Building a logger rate limiter is a common system design challenge. The goal is to prevent the same message from being displayed too frequently. My first approach was overly complex, using both a queue and a set to track messages. Then I realized a simple hash map was all I needed.

The key insight is that we only need to track the last timestamp for each unique message. If a message comes in and it's been more than the time limit since the last time we saw it, we can show it. Otherwise, it's a duplicate and should be rejected.

Understanding the Problem

We need to build a system that:

• Receives message requests with timestamps
• Decides whether to display each message
• A message should only be shown if it hasn't been shown in the last S seconds
• If the same message appears within S seconds, it's a duplicate and should be rejected

The challenge is doing this efficiently, especially when there are many different messages.

My First Approach

I thought I'd use a queue to store messages and a set to track duplicates, cleaning up old messages periodically.

class LoggerNaive {
  constructor(timeLimit) {
    this.queue = [];
    this.messageSet = new Set();
    this.limit = timeLimit;
  }

  shouldPrintMessage(timestamp, message) {
    // Remove old messages (older than timeLimit)
    while (
      this.queue.length > 0 &&
      timestamp - this.queue[0].timestamp >= this.limit
    ) {
      const old = this.queue.shift();
      this.messageSet.delete(old.message);
    }

    // Check if message is duplicate
    if (this.messageSet.has(message)) {
      return false;
    }

    // Add new message
    this.queue.push({ timestamp, message });
    this.messageSet.add(message);
    return true;
  }
}

This worked, but it was more complex than needed. I was maintaining both a queue and a set, and cleaning up old messages every time a new message arrived. The queue operations (shift) are O(n) in JavaScript arrays, making this inefficient.

The Simpler Approach

Then I realized: I only need to track the last timestamp for each message! If a message comes in and it's been more than S seconds since the last time, I can show it. Otherwise, it's a duplicate.

Here's my simpler solution:

class Logger {
  constructor(timeLimit) {
    this.requests = {}; // Map message to last timestamp
    this.limit = timeLimit;
  }

  shouldPrintMessage(timestamp, message) {
    // If message is new OR enough time has passed
    if (
      !this.requests[message] ||
      timestamp - this.requests[message] >= this.limit
    ) {
      this.requests[message] = timestamp; // Update last seen time
      return true;
    }
    return false; // Duplicate within time limit
  }
}

How It Works

The algorithm is straightforward:

1. Check if message exists: If the message isn't in our map, it's new - allow it
2. Check time difference: If the message exists, check if enough time has passed
3. Update timestamp: If we allow the message, update its timestamp
4. Return result: Return true if allowed, false if rejected

Step-by-Step Example

Let me trace through an example with timeLimit = 7:

const logger = new Logger(7);

// Timestamp 1: "hello" is new
logger.shouldPrintMessage(1, "hello"); 
// requests = {"hello": 1}
// Returns: true

// Timestamp 5: "hello" seen 4 seconds ago (< 7)
logger.shouldPrintMessage(5, "hello"); 
// Only 4 seconds passed, not enough
// Returns: false

// Timestamp 6: "world" is new
logger.shouldPrintMessage(6, "world"); 
// requests = {"hello": 1, "world": 6}
// Returns: true

// Timestamp 8: "hello" seen 7 seconds ago (>= 7)
logger.shouldPrintMessage(8, "hello"); 
// 7 seconds passed, enough time
// requests = {"hello": 8, "world": 6}
// Returns: true

// Timestamp 10: "world" seen 4 seconds ago (< 7)
logger.shouldPrintMessage(10, "world"); 
// Only 4 seconds passed, not enough
// Returns: false

Why This Approach Is Better

Simplicity

• Only one data structure (hash map) instead of two
• No need to clean up old entries - they're automatically overwritten
• Cleaner, more readable code

Efficiency

• Time: O(1) per operation (hash map lookup and update)
• Space: O(n) where n is the number of unique messages
• No queue operations that could be O(n)

Correctness

• Automatically handles the time window correctly
• No need to manually clean up old entries
• Simpler logic means fewer bugs

Complexity Analysis

Time Complexity: O(1) per operation

• Hash map lookup: O(1)
• Hash map update: O(1)
• No loops or iterations needed

Space Complexity: O(n)

• We store one timestamp per unique message
• In the worst case, all messages are unique: O(n)
• However, old entries are automatically overwritten when messages repeat

Common Pitfalls

When implementing this, watch out for:

1. Off-by-one errors: Make sure your comparison is >= not > (or vice versa depending on requirements)
2. Timestamp handling: Ensure timestamps are monotonically increasing
3. Edge cases: What happens with the first message? (Should be allowed)
4. Memory growth: In a real system, you might want to clean up very old entries to prevent memory leaks

Real-World Considerations

In a production system, you might want to add:

• Memory cleanup: Remove entries older than a certain threshold
• Bounded size: Limit the number of entries to prevent unbounded memory growth
• Thread safety: If multiple threads access the logger, add synchronization
• Persistence: Store the map to disk for durability

Key Takeaways

• Sometimes the simplest data structure (hash map) is the best choice
• We don't always need to track everything - just what matters
• Hash maps make O(1) lookups possible, perfect for this use case
• System design problems often have elegant solutions
• This pattern appears in many rate limiting problems

I found this problem really satisfying because the solution was much simpler than I initially thought. It's a great example of how the right data structure can make a problem much easier. The hash map approach is elegant, efficient, and exactly what you'd want in a production system.