Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input describes calls on a single-threaded CPU. Each log entry has a function id, an event type, and a timestamp:

function_id:start_or_end:timestamp

A function can call another function before it finishes. While the child function runs, the parent is paused. The goal is to return, for every function id, how much time that function spent actually executing, excluding time spent inside child calls.

The awkward detail is that end timestamps are inclusive. If a function starts at time 2 and ends at time 5, it runs for 4 units: 2, 3, 4, 5.

That inclusive ending is where most wrong answers lose one unit of time.

The stack idea

At any timestamp, only one function is actively running: the function on top of the call stack.

When a start log appears, the currently active function pauses. The new function becomes active, so it is pushed onto the stack.

When an end log appears, the function on top of the stack finishes. It is popped, and control returns to the previous function, if one exists.

So the stack tells us who owns each stretch of time. The remaining trick is to track the beginning of the current unassigned time stretch.

The timestamp boundary trick

Keep a variable called previous_timestamp.

It means:

“The next unit of time that has not yet been assigned to any function starts here.”

For a start event at timestamp t, the old top-of-stack function ran from previous_timestamp through t - 1. That is:

t - previous_timestamp

Then the new function starts exactly at t, so set previous_timestamp = t.

For an end event at timestamp t, the finishing function ran from previous_timestamp through t, inclusive. That is:

t - previous_timestamp + 1

After that, the next unassigned time unit is t + 1, so set previous_timestamp = t + 1.

This is the whole solution. The stack tracks nesting, and previous_timestamp prevents double-counting.

A small example

Consider these logs:

0:start:0
1:start:2
1:end:5
0:end:6

Function 0 starts at time 0, then pauses when function 1 starts at time 2. Function 0 gets the time interval [0, 1], which is 2 units.

Function 1 runs from [2, 5], which is 4 units because the end timestamp is inclusive.

Function 0 resumes after time 5, so the next unassigned timestamp is 6. It ends at 6, giving it one more unit. The final answer is:

[3, 4]

Python solution

from __future__ import annotations

from dataclasses import dataclass
from typing import List


@dataclass(frozen=True)
class LogEntry:
    function_id: int
    event_type: str
    timestamp: int


def parse_log_entry(raw_log: str) -> LogEntry:
    """Parse one LeetCode log line of the form 'id:start|end:timestamp'."""
    function_id_text, event_type, timestamp_text = raw_log.split(":")
    return LogEntry(
        function_id=int(function_id_text),
        event_type=event_type,
        timestamp=int(timestamp_text),
    )


class ExclusiveTimeCalculator:
    """Calculate exclusive execution time from sorted function logs."""

    def calculate(self, function_count: int, logs: List[str]) -> List[int]:
        exclusive_times = [0] * function_count
        active_function_stack: List[int] = []
        previous_timestamp = 0

        for raw_log in logs:
            entry = parse_log_entry(raw_log)

            if entry.event_type == "start":
                if active_function_stack:
                    paused_function_id = active_function_stack[-1]
                    exclusive_times[paused_function_id] += (
                        entry.timestamp - previous_timestamp
                    )

                active_function_stack.append(entry.function_id)
                previous_timestamp = entry.timestamp
                continue

            finished_function_id = active_function_stack.pop()

            # End timestamps are inclusive, so the finishing function owns the
            # current timestamp as well.
            exclusive_times[finished_function_id] += (
                entry.timestamp - previous_timestamp + 1
            )
            previous_timestamp = entry.timestamp + 1

        return exclusive_times


class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        calculator = ExclusiveTimeCalculator()
        return calculator.calculate(n, logs)

Why this works

The algorithm maintains this invariant:

before processing each log, all time units before previous_timestamp have already been assigned to exactly one function, and the current active function is on top of the stack.

For a start event, the new function cannot start until the current active function receives all unassigned time before that timestamp. Adding timestamp - previous_timestamp assigns exactly that interval, then the new function becomes active.

For an end event, the function on top of the stack must be the one that is finishing. Adding timestamp - previous_timestamp + 1 assigns its final active interval, including the end timestamp. Moving previous_timestamp to timestamp + 1 ensures the parent function resumes only after the child has fully completed.

Each log is processed once, and each function call is pushed and popped once. The runtime is O(number of logs). The result array uses O(n) space, and the stack uses O(call depth) extra space.

Interview follow-ups

What if the logs may be malformed?

The same core algorithm still applies, but the parser should become stricter. It should validate that every log has exactly three fields, the event type is either start or end, the function id is in range, timestamps are nondecreasing, and every end matches the function currently on top of the stack.

Those checks do not change the asymptotic complexity. The runtime remains linear in the number of logs, and the extra memory is still dominated by the call stack. The tradeoff is that production validation makes the code more verbose, while LeetCode can stay lean because the input is guaranteed valid.

How would the solution change if end timestamps were exclusive?

If an end timestamp meant the function stopped just before that timestamp, then the + 1 would disappear. A function ending at t would own the interval from previous_timestamp through t - 1, so the added duration would be t - previous_timestamp, and the next unassigned timestamp would be t.

The stack logic stays the same because nested calls still behave like nested intervals. Only the boundary convention changes. This is a good follow-up because it tests whether the candidate understands why the original solution uses timestamp + 1 after an end event.

Can this be solved without a stack?

Not in the general nested-call case. The algorithm needs to know which function resumes after a child call finishes. That is exactly last-in, first-out behavior, so a stack is the natural data structure.

If the input guaranteed that calls never nested, then a stack would be unnecessary because each start would be followed directly by its own end. But with nested calls, removing the stack would lose the parent context. The best practical solution keeps the stack and processes the logs in one pass.

What if several threads could run at the same time?

The original problem assumes a single-threaded CPU, which means each unit of time belongs to only one active function. With multiple threads, each thread would need its own call stack and timestamp boundary because calls on one thread should not pause calls on another thread.

The expected approach is to group or stream logs by thread id, apply the same single-threaded algorithm independently per thread, and then aggregate exclusive time by function id. The complexity stays linear in the total number of logs if logs are already ordered per thread. If the logs arrive globally interleaved and not sorted by thread timestamp, an additional sort or buffering step may be needed.

Practical takeaway

This problem is mostly about assigning time intervals cleanly.

Use a stack to know which function is active, and use previous_timestamp to remember where the next unassigned interval begins. On start, assign time before the new call. On end, assign time through the inclusive end timestamp. That gives the optimal one-pass solution.