Leetcode - Logger Rate Limiter Solution

Building a logger rate limiter means deciding whether a message can be shown at a given timestamp. The decision only depends on when that message was last accepted. My first approach used both a queue and a set, but a hash map is enough for the rule.

The rule to enforce

For each message, accept the first request. Later requests are accepted only when at least timeLimit seconds have passed since the last accepted request. Rejected requests do not move the stored timestamp.

I first used a queue for timestamps and a set for currently active messages. Old entries were removed before each request:

class LoggerNaive {
  constructor(timeLimit = 10) {
    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;
  }
}

The queue and set version is correct, but it maintains two structures and cleans the queue for every request. shift on a JavaScript array is O(n), so the cleanup can dominate the work.

Last seen timestamps

I then stored only the last accepted timestamp for each message:

class Logger {
  constructor(timeLimit = 10) {
    this.requests = Object.create(null); // Message names must not inherit object properties
    this.limit = timeLimit;
  }

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

The method checks whether the stored timestamp is undefined or whether timestamp - lastTimestamp >= timeLimit. Timestamp zero is a valid stored value. An allowed request updates the map and returns true. A rejected request leaves the previous timestamp unchanged and returns false.

The object has no prototype, so message names such as toString and __proto__ behave like other keys. The default interval is ten seconds. The example below supplies seven seconds explicitly.

Trace and operational costs

With timeLimit = 7, the calls behave as follows:

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

The hash map replaces two coordinated structures with one last seen record. Repeated messages overwrite their previous timestamp instead of adding queue entries.

The hash map gives O(1) average lookup and update time per request. It stores one timestamp per unique message, so the space complexity is O(n), where n is the number of unique messages.

Boundaries for a service

The comparison must match the problem's boundary rule. The implementation uses >= to accept a request at the exact limit. A comparison with > would reject it. Timestamps should follow the problem's ordering assumptions, and the first request for a message should be allowed.

The simple class keeps entries indefinitely. A service that runs continuously may need to remove old messages and limit the map size. Shared access from multiple threads may require synchronization. If the state must survive a restart, the service also needs persistent storage.

The rate limiter needs one fact per message: the last accepted timestamp. A hash map records that fact directly, making the basic operation constant time while leaving cleanup and concurrency policy to the surrounding service.