Logger Rate Limiter

Easy Design Data Structures Hash Map + Array Original on LeetCode

Logger Rate Limiter is a easy design data structures problem solved with the hash map + array pattern. The best approach, optimal (queue of recent prints + set), runs in O(1) amortized per call time and O(w) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (scan every printed message) up.

Problem

Build a Logger that receives a stream of log messages, each with a timestamp in seconds, and decides whether each one should actually be printed. The rule: a message may be printed only if the same message was not printed during the previous 10 seconds. Once a message is printed at time t, every copy of it arriving before time t + 10 is suppressed.

Implement Logger(), which starts with nothing printed, and shouldPrintMessage(timestamp, message), which returns true if the message is printed now and false if it is suppressed. A suppressed message does not count as printed.

Calls arrive in non-decreasing order of timestamp, and several calls may share the same timestamp.

Examples

Example 1

Input
Logger(), shouldPrintMessage(1, "boot"), shouldPrintMessage(3, "disk"), shouldPrintMessage(5, "boot"), shouldPrintMessage(11, "boot"), shouldPrintMessage(12, "disk"), shouldPrintMessage(13, "disk")
Output
true, true, false, true, false, true
Why
"boot" printed at 1 is blocked until 11, so 5 is refused and 11 is allowed; "disk" printed at 3 is blocked until 13, so 12 is refused and 13 is allowed.

Example 2

Input
Logger(), shouldPrintMessage(7, "a"), shouldPrintMessage(7, "a"), shouldPrintMessage(16, "a"), shouldPrintMessage(17, "a"), shouldPrintMessage(27, "a")
Output
true, false, false, true, true
Why
A refused call does not restart the 10-second wait: after printing at 7 the next print is allowed at 17, and after that at 27.

Constraints

  • 0 <= timestamp <= 10^9
  • Calls arrive in chronological order: each timestamp is greater than or equal to the previous one.
  • 1 <= message.length <= 30, lowercase English letters.
  • At most 10^4 calls to shouldPrintMessage.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan every printed message)O(n) per callO(n)
Hash map of next allowed timeO(1) per callO(m)
Optimal (queue of recent prints + set)O(1) amortized per callO(w)

1Brute force (scan every printed message)

TimeO(n) per callEach call scans every message printed so far.
SpaceO(n)Every printed message is stored forever.

Keep a list of every message that was actually printed, with its time. For a new call, scan the whole list for the same message printed less than 10 seconds ago.

  1. Keep two parallel lists: print times and printed messages.
  2. For a call (t, m), scan all entries; if one has message m and time > t - 10, return false.
  3. Otherwise append (t, m) and return true.
class Logger {
    private final List<Integer> times = new ArrayList<>();
    private final List<String> messages = new ArrayList<>();

    public Logger() {
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        for (int i = 0; i < times.size(); i++) {
            if (messages.get(i).equals(message) && times.get(i) > timestamp - 10) {
                return false;
            }
        }
        times.add(timestamp);
        messages.add(message);
        return true;
    }
}

2Hash map of next allowed time

TimeO(1) per callOne hash lookup and at most one insert per call (on average).
SpaceO(m)One entry per distinct message ever printed, m of them, even ones that are long expired.

Store, for each message, the earliest second at which it may be printed again. A call is allowed when the current time has reached that second; only then is the deadline moved to timestamp + 10.

  1. Look up message in the map (missing means it was never printed).
  2. If it is present and timestamp < stored time, return false.
  3. Otherwise store timestamp + 10 for the message and return true.
class Logger {
    private final Map<String, Integer> nextAllowed = new HashMap<>();

    public Logger() {
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        Integer next = nextAllowed.get(message);
        if (next != null && timestamp < next) {
            return false;
        }
        nextAllowed.put(message, timestamp + 10);
        return true;
    }
}

3Optimal (queue of recent prints + set)

TimeO(1) amortized per callEvery printed message is pushed once and popped at most once; the set operations are O(1) on average.
SpaceO(w)Only prints from the last 10 seconds are kept: w is the number of distinct messages printed in any 10-second window.

Only prints from the last 10 seconds can block anything. Keep those prints in a queue in time order plus a set of their messages. Before answering, pop prints that are 10 or more seconds old from the front and remove them from the set; the message is allowed exactly when it is not in the set. Same O(1) amortized time as the map, but memory stays bounded by the messages printed in the last 10 seconds.

  1. While the queue's front was printed at time <= timestamp - 10, pop it and remove its message from the set.
  2. If message is in the set, return false.
  3. Otherwise push (timestamp, message), add message to the set, and return true.
class Logger {
    private final Deque<Integer> times = new ArrayDeque<>();
    private final Deque<String> messages = new ArrayDeque<>();
    private final Set<String> recent = new HashSet<>();

    public Logger() {
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        while (!times.isEmpty() && times.peekFirst() <= timestamp - 10) {
            times.pollFirst();
            recent.remove(messages.pollFirst());
        }
        if (recent.contains(message)) {
            return false;
        }
        times.addLast(timestamp);
        messages.addLast(message);
        recent.add(message);
        return true;
    }
}

Edge cases to test

  • The same message twice at the same second: only the first is printed
  • A repeat exactly 10 seconds later is allowed; 9 seconds later is not
  • A refused message must not push its own deadline further
  • Different messages never block each other

Hints

Hint 1

For each message you only need one fact: the earliest time it may be printed again.

Hint 2

A hash map from message to that time answers every call in O(1).

Hint 3

To keep memory small, notice that a message printed more than 10 seconds ago can be forgotten entirely. Since timestamps only grow, a queue of recent prints lets you drop old ones from the front.

FAQ

What is the best time complexity for Logger Rate Limiter?

Optimal (queue of recent prints + set) runs in O(1) amortized per call time and O(w) extra space. Every printed message is pushed once and popped at most once; the set operations are O(1) on average.

Which pattern does Logger Rate Limiter use?

It is a design data structures problem that uses the hash map + array pattern. Other problems with the same pattern: Insert Delete GetRandom O(1), Insert Delete GetRandom O(1) - Duplicates allowed, Design Parking System.

Is there a brute force solution for Logger Rate Limiter?

Yes. Brute force (scan every printed message) takes O(n) per call time and O(n) space. Keep a list of every message that was actually printed, with its time.

Which edge cases should I test for Logger Rate Limiter?

The same message twice at the same second: only the first is printed; A repeat exactly 10 seconds later is allowed; 9 seconds later is not; A refused message must not push its own deadline further; Different messages never block each other.