Skip to content

359. Logger Rate Limiter 👍

Approach 1: Queue + Set

  • Time:
    • Constructor: $O(1)$
    • shouldPrintMessage(timestamp: int, message: str): $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Logger {
 public:
  bool shouldPrintMessage(int timestamp, string message) {
    // Remove the messages that are 10 seconds from the current timestamp.
    while (!messageQueue.empty()) {
      const auto [headTimestamp, headMessage] = messageQueue.front();
      if (timestamp < headTimestamp + 10)
        break;
      messageQueue.pop_front();
      messageSet.erase(headMessage);
    }

    if (messageSet.contains(message))
      return false;

    messageQueue.emplace_back(timestamp, message);
    messageSet.insert(message);
    return true;
  }

 private:
  // [(timestamp, message)]
  deque<pair<int, string>> messageQueue;
  unordered_set<string> messageSet;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Logger {
  public boolean shouldPrintMessage(int timestamp, String message) {
    // Remove the messages that are 10 seconds from the current timestamp.
    while (!messageQueue.isEmpty()) {
      Pair<Integer, String> head = messageQueue.peekFirst();
      if (timestamp - head.getKey() < 10)
        break;
      messageQueue.pollFirst();
      messageSet.remove(head.getValue());
    }

    if (messageSet.contains(message))
      return false;

    messageQueue.offerLast(new Pair<>(timestamp, message));
    messageSet.add(message);
    return true;
  }

  // [(timestamp, message)]
  private Deque<Pair<Integer, String>> messageQueue = new ArrayDeque<>();
  private Set<String> messageSet = new HashSet<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Logger:
  def __init__(self):
    # [(timestamp, message)]
    self.messageQueue = collections.deque()
    self.messageSet = set()

  def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
    # Remove the messages that are 10 seconds from the current timestamp.
    while self.messageQueue:
      headTimestamp, headMessage = self.messageQueue[0]
      if timestamp < headTimestamp + 10:
        break
      self.messageQueue.popleft()
      self.messageSet.remove(headMessage)

    if message in self.messageSet:
      return False

    self.messageQueue.append((timestamp, message))
    self.messageSet.add(message)
    return True

Approach 2: Map (unrealistic)

  • Time:
    • Constructor: $O(1)$
    • shouldPrintMessage(timestamp: int, message: str): $O(1)$
  • Space: $O(|\texttt{shouldPrintMessage()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Logger {
 public:
  bool shouldPrintMessage(int timestamp, string message) {
    if (timestamp < okTime[message])
      return false;

    okTime[message] = timestamp + 10;
    return true;
  }

 private:
  unordered_map<string, int> okTime;  // {message: ok time}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Logger {
  public boolean shouldPrintMessage(int timestamp, String message) {
    if (timestamp < okTime.getOrDefault(message, 0))
      return false;

    okTime.put(message, timestamp + 10);
    return true;
  }

  private Map<String, Integer> okTime = new HashMap<>(); // {message: ok time}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Logger:
  def __init__(self):
    self.okTime = {}  # {message: ok time}

  def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
    if timestamp < self.okTime.get(message, 0):
      return False

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