Constraints

• 0 <= len(logs) <= 2 * 10^5
• Each log is a tuple `(id, event, timestamp)`
• `event` is either `'START'` or `'END'`
• Timestamps are integers and may be equal
• The given log order is valid and represents properly nested calls

Examples

Solution

def solution(logs):
    from collections import defaultdict

    times = defaultdict(int)
    stack = []
    prev_time = None

    for fid, event, timestamp in logs:
        times.setdefault(fid, 0)

        if prev_time is None:
            prev_time = timestamp

        if stack:
            times[stack[-1]] += timestamp - prev_time

        if event == 'START':
            stack.append(fid)
        elif event == 'END':
            if not stack or stack[-1] != fid:
                raise ValueError('Invalid log sequence')
            stack.pop()
        else:
            raise ValueError('Unknown event type')

        prev_time = timestamp

    if stack:
        raise ValueError('Unclosed function calls')

    return dict(times)

Explanation

Time complexity: O(n), where n is the number of log entries — a single pass with O(1) work per entry (each id pushed/popped at most once).. Space complexity: O(u + d), where u is the number of distinct ids (the `times` map) and d is the maximum nesting depth (the `stack`)..

Hints

1. Keep a stack of currently active function calls.
2. When a new log at time `t` arrives, the function on top of the stack has been running since the previous timestamp.

Constraints

• 0 <= len(logs) <= 2 * 10^5
• 0 <= max_delay <= len(logs)
• Each log is a tuple `(id, event, timestamp)`
• `event` is either `'START'` or `'END'`
• Each log is at most `max_delay` positions later than its correct position in the stable timestamp order
• After stable sorting by `(timestamp, arrival_index)`, the call sequence is valid and properly nested

Examples

Solution

def solution(logs, max_delay):
    from collections import defaultdict
    import heapq

    if max_delay < 0:
        raise ValueError('max_delay must be non-negative')

    times = defaultdict(int)
    stack = []
    prev_time = None
    heap = []

    def process(entry):
        nonlocal prev_time
        fid, event, timestamp = entry
        times.setdefault(fid, 0)

        if prev_time is None:
            prev_time = timestamp

        if stack:
            times[stack[-1]] += timestamp - prev_time

        if event == 'START':
            stack.append(fid)
        elif event == 'END':
            if not stack or stack[-1] != fid:
                raise ValueError('Invalid log sequence after reordering')
            stack.pop()
        else:
            raise ValueError('Unknown event type')

        prev_time = timestamp

    for arrival_index, entry in enumerate(logs):
        timestamp = entry[2]
        heapq.heappush(heap, (timestamp, arrival_index, entry))

        if len(heap) > max_delay + 1:
            _, _, smallest = heapq.heappop(heap)
            process(smallest)

    while heap:
        _, _, smallest = heapq.heappop(heap)
        process(smallest)

    if stack:
        raise ValueError('Unclosed function calls')

    return dict(times)

Explanation

Time complexity: O(n log(max_delay + 1)). Space complexity: O(max_delay + d + u), where d is the maximum corrected call-stack depth and u is the number of distinct ids.

Hints

1. If every item is at most `k` positions late, a min-heap of size `k + 1` can emit the next correct item online.
2. Once a corrected log is emitted, the exclusive-time accounting is the same stack-based idea as in Part 1.

Constraints

• 0 <= len(events) <= 2 * 10^5
• 1 <= N <= 2 * 10^5
• Event values only need to support equality comparison
• Indices are 0-based

Examples

Solution

def solution(events, N):
    if N <= 0:
        raise ValueError('N must be positive')

    run_value = None
    run_length = 0

    for i, value in enumerate(events):
        if value == run_value:
            run_length += 1
        else:
            run_value = value
            run_length = 1

        if run_length == N:
            return i - N + 1

    return -1

Explanation

Time complexity: O(n), where n = len(events) — one pass, O(1) work per element. Space complexity: O(1) — only two scalar variables, independent of input size.

Hints

1. You do not need a sliding-window frequency map; only the current run matters.
2. As soon as the current run length reaches `N`, you have found the earliest valid start.