LeetCode 636: Exclusive Time of Functions

Problem Restatement

We are given n functions with IDs from 0 to n - 1.

We also receive a list of logs. Each log has this format:

"{function_id}:{start_or_end}:{timestamp}"

For example:

"0:start:3"

means function 0 starts at the beginning of timestamp 3.

"1:end:5"

means function 1 ends at the end of timestamp 5.

The CPU is single-threaded, so only one function runs at a time. A function may call another function, including itself recursively.

We need to return the exclusive time of every function.

Exclusive time means the time spent running that function itself, excluding time spent inside functions it called.

Input and Output

Example function shape:

def exclusiveTime(n: int, logs: list[str]) -> list[int]:
    ...

Examples

Example 1:

n = 2
logs = [
    "0:start:0",
    "1:start:2",
    "1:end:5",
    "0:end:6",
]

Timeline:

Function 0 runs at timestamps 0, 1, and 6.

So its exclusive time is:

3

Function 1 runs at timestamps 2, 3, 4, and 5.

So its exclusive time is:

4

The answer is:

[3, 4]

First Thought: Simulate Every Timestamp

A direct approach is to simulate time unit by time unit.

At each timestamp, we track which function is running and add 1 to that function’s time.

This is conceptually simple, but timestamps can be large. We do not want to iterate over every single timestamp.

Instead, we should process intervals between logs.

Key Insight

At any time, the currently running function is the one at the top of the call stack.

When a function starts, it pauses the current top function.

When a function ends, it is popped from the stack, and the previous function resumes.

We also keep a variable prev_time, which means:

the first timestamp not yet assigned to any function

When we see a new log at timestamp t, the function currently on top of the stack has been running from prev_time up to just before t if this is a start log.

For an end log, the function runs from prev_time through t, because end timestamps are inclusive.

That inclusive end is the main detail.

Algorithm

Create:

answer = [0] * n
stack = []
prev_time = 0

For each log:

1. Parse function_id, event, and timestamp.
2. If the event is "start":
   1. If the stack is not empty, add timestamp - prev_time to the function on top.
   2. Push the new function ID.
   3. Set prev_time = timestamp.
3. If the event is "end":
   1. Pop the function from the stack.
   2. Add timestamp - prev_time + 1 to that function.
   3. Set prev_time = timestamp + 1.

Return answer.

Implementation

class Solution:
    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:
        answer = [0] * n
        stack = []
        prev_time = 0

        for log in logs:
            function_id_str, event, timestamp_str = log.split(":")
            function_id = int(function_id_str)
            timestamp = int(timestamp_str)

            if event == "start":
                if stack:
                    answer[stack[-1]] += timestamp - prev_time

                stack.append(function_id)
                prev_time = timestamp

            else:
                finished_function = stack.pop()
                answer[finished_function] += timestamp - prev_time + 1
                prev_time = timestamp + 1

        return answer

Code Explanation

The result array stores exclusive time for each function:

answer = [0] * n

The stack stores active function calls:

stack = []

The top of the stack is the function currently running.

The variable:

prev_time = 0

marks the next timestamp that still needs to be counted.

For a start log:

if event == "start":

the currently running function, if any, has run from prev_time to timestamp - 1.

So we add:

answer[stack[-1]] += timestamp - prev_time

Then we push the newly started function:

stack.append(function_id)

and reset prev_time:

prev_time = timestamp

For an end log:

finished_function = stack.pop()

the ending function has run from prev_time through timestamp.

That is:

timestamp - prev_time + 1

The +1 is required because the end timestamp is included.

After the function ends at the end of timestamp, the next available time is:

timestamp + 1

So we set:

prev_time = timestamp + 1

Correctness

The stack always represents the active function calls that have started but have not ended. Since the CPU is single-threaded, the function at the top of the stack is the only function running.

Whenever a "start" log appears at timestamp t, the previous top function stops running at the beginning of t. Therefore, it has executed exactly t - prev_time units since the last processed timestamp, and the algorithm adds that amount to its exclusive time.

Whenever an "end" log appears at timestamp t, the top function continues running through the end of timestamp t. Therefore, it has executed exactly t - prev_time + 1 units since the last processed timestamp, and the algorithm adds that amount to its exclusive time before popping it from the stack.

After each log, prev_time is updated to the next timestamp that has not yet been counted. This ensures every time unit is charged exactly once to the function running during that time.

Thus the algorithm computes exactly the exclusive execution time for every function.

Complexity

Let m be the number of logs.

The stack depth is at most the number of active nested calls.

Testing

def run_tests():
    s = Solution()

    assert s.exclusiveTime(2, [
        "0:start:0",
        "1:start:2",
        "1:end:5",
        "0:end:6",
    ]) == [3, 4]

    assert s.exclusiveTime(1, [
        "0:start:0",
        "0:end:0",
    ]) == [1]

    assert s.exclusiveTime(2, [
        "0:start:0",
        "0:start:2",
        "0:end:5",
        "1:start:6",
        "1:end:6",
        "0:end:7",
    ]) == [7, 1]

    assert s.exclusiveTime(2, [
        "0:start:0",
        "0:end:1",
        "1:start:2",
        "1:end:3",
    ]) == [2, 2]

    print("all tests passed")

run_tests()

Test meaning: