Problem Statement

Design a log aggregation system that records timestamped events grouped by key, and supports counting how many events of a given key occurred within a time range.

This models a common backend pattern: counting error rates, request frequencies, or event occurrences within a sliding window.

Implement the LogAggregator class:

• LogAggregator() initializes the system.
• void record(int timestamp, string key) records an event with the given timestamp and key. Timestamps are guaranteed to be in non-decreasing order across all calls.
• int count(string key, int start, int end) returns the number of events with the given key that have a timestamp in the inclusive range [start, end].

Additional information

• 1 <= timestamp <= 10^9
• key consists of lowercase English letters and has length between 1 and 20.
• Timestamps across calls to record are in non-decreasing order.
• 1 <= start <= end <= 10^9
• Multiple events can share the same timestamp and key.
• At most 50,000 calls will be made to record and count combined.

Example 1:

Input:
["LogAggregator", "record", "record", "record", "record", "count", "count", "count"]
[[], [1, "error"], [2, "error"], [3, "warn"], [5, "error"], ["error", 1, 5], ["warn", 1, 5], ["info", 1, 5]]

Output: [null, null, null, null, null, 3, 1, 0]

Explanation:

• Three "error" events at t=1,2,5 and one "warn" at t=3.
• count("error", 1, 5) returns 3 (all error events fall in range).
• count("warn", 1, 5) returns 1.
• count("info", 1, 5) returns 0 (no "info" events recorded).

Example 2:

Input:
["LogAggregator", "record", "record", "record", "record", "record", "count", "count"]
[[], [1, "a"], [1, "a"], [1, "b"], [2, "a"], [2, "b"], ["a", 1, 1], ["a", 1, 2]]

Output: [null, null, null, null, null, null, 2, 3]

Explanation: Key "a" appears twice at t=1 and once at t=2. Range [1,1] has 2 events, range [1,2] has 3.

Brute Force (Linear Scan)

Intuition

Store all events in a hash map from key to list of timestamps. On each count query, iterate through the key's entire timestamp list and count how many fall in the range.

Algorithm

1. On record(timestamp, key): append timestamp to the list for key.
2. On count(key, start, end): iterate through the list for key, count timestamps where start <= t <= end.

from collections import defaultdict

class LogAggregator:
    def __init__(self):
        self.logs = defaultdict(list)

    def record(self, timestamp, key):
        self.logs[key].append(timestamp)

    def count(self, key, start, end):
        return sum(1 for t in self.logs[key] if start <= t <= end)

Time & Space Complexity

• Time complexity: O(1) per record, O(n) per count

• Reason: Each count query scans all timestamps for that key.

• Space complexity: O(n)

• Reason: All timestamps are stored.

Hash Map + Binary Search (Optimal)

Intuition

Since timestamps arrive in non-decreasing order, each key's timestamp list is already sorted. We can use binary search to find the boundaries of the range [start, end] in O(log n) time instead of scanning the whole list.

bisect_left(timestamps, start) gives the index of the first timestamp >= start. bisect_right(timestamps, end) gives the index just past the last timestamp <= end. The difference is the count.

Algorithm

1. On record(timestamp, key): append timestamp to the list for key.
2. On count(key, start, end): use bisect_left and bisect_right on the sorted list to find the range boundaries. Return right - left.

from collections import defaultdict
import bisect

class LogAggregator:
    def __init__(self):
        self.logs = defaultdict(list)

    def record(self, timestamp, key):
        self.logs[key].append(timestamp)

    def count(self, key, start, end):
        if key not in self.logs:
            return 0
        timestamps = self.logs[key]
        left = bisect.bisect_left(timestamps, start)
        right = bisect.bisect_right(timestamps, end)
        return right - left

Time & Space Complexity

• Time complexity: O(1) per record, O(log n) per count

• Reason: Binary search on a sorted list of n timestamps takes O(log n).

• Space complexity: O(n)

• Reason: All timestamps are stored.