Logger Rate Limiter
Understanding the Problem
We are building a rate limiter for log messages. When a message arrives, we need to decide: has this exact message been printed within the last 10 seconds? If yes, suppress it. If no (or we have never seen it), print it and record the timestamp.
The important detail is the 10-second window. If "foo" was last printed at time 1, it can be printed again at time 11 or later, but not at time 10. The check is currentTimestamp >= lastTimestamp + 10, or equivalently, currentTimestamp - lastTimestamp >= 10.
Since messages arrive in chronological order, we never receive a message with a timestamp earlier than one we have already processed. We can overwrite a message's stored timestamp without corrupting any earlier decision.
The operations we need are fast lookup by message string and storage of one timestamp per message. A hash map provides both in O(1).
Key Constraints:
0 <= timestamp <= 10^9-- Timestamps fit in a 32-bit signed integer, andtimestamp + 10stays well below the2^31 - 1limit, so there is no overflow risk in the cooldown check.- Every
timestampis non-decreasing -- We never receive out-of-order messages, so we do not need to handle retroactive changes to a rate-limit window. This ordering also lets the sliding-window approach below evict expired entries from one end only. 1 <= message.length <= 30-- Messages are short strings, so hashing one is a bounded-cost operation we can treat as O(1).- At most
10^4calls -- An O(n) scan per call would reach 10^8 operations, which is borderline. A hash map brings each call to O(1).
Approach 1: Brute Force (Store All Messages with Timestamps)
Intuition
Store every printed (timestamp, message) pair. When a new message arrives, scan the stored pairs to find whether the same message was printed within the last 10 seconds.
This wastes both time and space. We keep every printed pair even though only the most recent occurrence of each message affects the decision, and we re-scan the entire history on every call.
Algorithm
- Initialize an empty list to store (timestamp, message) pairs.
- On each
shouldPrintMessage(timestamp, message)call: - Scan the list backward looking for the same message.
- If found with a timestamp within the last 10 seconds (i.e.,
timestamp - foundTimestamp < 10), return false. - If not found within 10 seconds (or not found at all), add the pair to the list and return true.
Example Walkthrough
Input:
For each call, we scan the stored list backward to find the most recent occurrence of the same message. If that occurrence is within 10 seconds, reject; otherwise add the pair and allow.
(1, "foo"): list empty, no match. Add(1, "foo"). Return true. List:[(1,"foo")].(2, "bar"): scan back, no "bar". Add(2, "bar"). Return true. List:[(1,"foo"),(2,"bar")].(3, "foo"): scan back, match at timestamp 1.3 - 1 = 2 < 10, still in cooldown. Return false. List unchanged.(8, "bar"): scan back, match at timestamp 2.8 - 2 = 6 < 10. Return false. List unchanged.(10, "foo"): scan back, match at timestamp 1.10 - 1 = 9 < 10. Return false. List unchanged.(11, "foo"): scan back, match at timestamp 1.11 - 1 = 10, not less than 10, so the cooldown has expired. Add(11, "foo"). Return true.
The returned sequence is [true, true, false, false, false, true].
Output:
Code
- Time Complexity: O(n) per call, where n is the number of messages printed so far. In the worst case, we scan through all stored pairs before finding a match or reaching the beginning.
- Space Complexity: O(n) where n is the total number of printed messages. We never remove old entries, so the list grows forever.
The linear search exists only because a list cannot find a specific message's last print time directly. A hash map keyed by the message string removes that scan, dropping each call to O(1).
Approach 2: Hash Map (Expiry per Message)
Intuition
Use a hash map where the key is the message string and the value is the next allowed timestamp for that message. When a message arrives at time t, check whether t is at least the stored next-allowed time. If the message is not in the map, it has never been printed, so allow it.
When a message is allowed, set its next-allowed timestamp to t + 10. Each subsequent call then needs one map lookup and one comparison, with no scanning and no stored history.
Storing the cooldown expiry rather than the last-seen time makes the check a single comparison, timestamp >= map.get(message), instead of timestamp - map.get(message) >= 10. Both are equivalent; the expiry form avoids a subtraction.
The approach relies on timestamps arriving in non-decreasing order. Once we write map[message] = t + 10, no later call can carry a timestamp smaller than t, so the stored expiry can never become stale relative to a future call. A message is allowed exactly when its previous expiry has passed, which is the definition of the 10-second cooldown. If timestamps could arrive out of order, a late-arriving earlier event might need to overwrite a larger stored value, and a single timestamp per message would no longer suffice.
Algorithm
- Initialize an empty hash map that maps message strings to their next allowed timestamp.
- On each
shouldPrintMessage(timestamp, message)call: - Look up the message in the map.
- If the message exists and
timestamp < nextAllowed, return false (still in cooldown). - Otherwise, update the map: set
map[message] = timestamp + 10. - Return true.
Example Walkthrough
Code
- Time Complexity: O(1) per call. Hash map lookup, comparison, and insertion are all O(1) amortized. Hashing a message of length up to 30 is a bounded-cost operation.
- Space Complexity: O(D) where D is the number of distinct messages ever seen. Within the problem's 10^4 calls this is at most 10^4 entries.
The space bound names the limitation of this approach: it stores one entry per distinct message and never removes any of them. A message printed once at timestamp 5 keeps its map entry forever, even if it never appears again. For a bounded test that is fine, but a logger that runs for months over a large vocabulary of distinct messages accumulates an entry per message and the map grows without bound.
The cooldown only depends on messages seen in the last 10 seconds. Anything older than timestamp - 10 can never cause a rejection again, so its entry is dead weight. The next approach bounds memory to the messages active within the current window.
Approach 3: Queue + Set Sliding Window
Intuition
A message can only suppress a future message if it was printed within the last 10 seconds. So the only state worth keeping is the set of messages printed in the current 10-second window. Track that set, and as time advances, discard messages whose print time has fallen out of the window.
A queue holds the printed (timestamp, message) events in arrival order. Because timestamps are non-decreasing, the oldest events sit at the front, so expiry happens from the front only. A companion set holds the messages currently in the queue, giving O(1) membership checks. On each call, first evict everything older than the window, then test membership.
Algorithm
- Keep a queue of
(timestamp, message)events and a set of the messages currently in the queue. - On each
shouldPrintMessage(timestamp, message)call: - While the queue is non-empty and its front event has
frontTimestamp <= timestamp - 10, remove the front event and erase its message from the set. (An event printed atfrontTimestampblocks reprints untilfrontTimestamp + 10; oncetimestamp >= frontTimestamp + 10, it can no longer block anything.) - If
messageis in the set, it was printed within the window, so return false. - Otherwise add
(timestamp, message)to the back of the queue, addmessageto the set, and return true.
Because messages arrive in non-decreasing timestamp order, a single message is never in the queue more than once: it is only enqueued when absent from the set, and it stays in the set until evicted.
Example Walkthrough
We trace the same calls. The queue holds events still inside the window; inWindow is the set of their messages.
(1, "foo"): queue empty, nothing to evict. "foo" not in set. Enqueue. Queue:[(1,foo)], set{foo}. Return true.(2, "bar"): front is(1,foo);1 <= 2 - 10 = -8? No, keep it. "bar" not in set. Enqueue. Queue:[(1,foo),(2,bar)], set{foo,bar}. Return true.(3, "foo"): evict check1 <= 3 - 10 = -7? No. "foo" is in set. Return false. State unchanged.(8, "bar"): evict check1 <= 8 - 10 = -2? No. "bar" is in set. Return false.(10, "foo"): evict check1 <= 10 - 10 = 0? No. "foo" is in set. Return false.(11, "foo"): evict check1 <= 11 - 10 = 1? Yes. Remove(1,foo), set becomes{bar}. Next front(2,bar):2 <= 1? No, stop. "foo" not in set now. Enqueue. Queue:[(2,bar),(11,foo)], set{bar,foo}. Return true.
The returned sequence is [true, true, false, false, false, true], matching the other approaches. After the last call the queue holds only (2,bar) and (11,foo), not the rejected attempts, so memory tracks the active window rather than all history.
Code
- Time Complexity: O(1) amortized per call. Each event is enqueued once and dequeued once over the lifetime of the logger, so the eviction loop does O(1) work per call when averaged across all calls. The membership check and insertion are O(1).
- Space Complexity: O(W) where W is the number of distinct messages printed within any 10-second window, rather than all distinct messages ever seen. For a long-running logger over a large message vocabulary, this is the practical advantage over Approach 2.
Approach 2 is the standard answer for the LeetCode constraints because it is shorter and the bounded 10^4 calls make its unbounded growth a non-issue. Approach 3 is what a long-running service would use, since its memory is tied to recent activity instead of total history. The tradeoff is more state (a queue plus a set) and amortized rather than strict O(1) per call.