LeetCode 636 - Exclusive Time of Functions

LeetCode Problem 636

Difficulty: 🟡 Medium
Topics: Array, Stack

Solution

Problem Understanding

This problem models how functions execute on a single-threaded CPU. Since the CPU is single-threaded, only one function can actively execute at any given moment. However, functions may call other functions, including recursive calls to themselves. Whenever one function calls another, the currently running function pauses, and the newly called function begins executing immediately.

The input consists of:

• An integer n, representing the total number of distinct function IDs from 0 to n - 1

• A list of log strings, where each log records:

• the function ID

• whether the function started or ended

• the timestamp of the event

Each log follows this format:

"{function_id}:{start|end}:{timestamp}"

A key detail is how timestamps work:

• "start" means the function begins execution at the beginning of that timestamp
• "end" means the function finishes execution at the end of that timestamp

This means end timestamps are inclusive. If a function starts at time 2 and ends at time 5, it executes for:

5 - 2 + 1 = 4

The goal is to compute the exclusive execution time for each function. Exclusive time means the amount of time a function spends actively running, excluding time spent inside child function calls.

The constraints are relatively small:

• n <= 100
• logs.length <= 500

This means even less optimized approaches may pass, but the problem is designed to test stack simulation and careful timestamp accounting.

Several edge cases are especially important:

• Recursive calls, where the same function appears multiple times in the stack
• Functions ending immediately after starting
• Nested calls with multiple levels
• Correct handling of inclusive end timestamps
• Resuming parent execution after child completion

The problem guarantees:

• Every "start" has a matching "end"
• Logs are valid and ordered chronologically
• No two start events share the same timestamp
• No two end events share the same timestamp

These guarantees allow us to safely simulate execution with a stack.

Approaches

Brute Force Approach

A brute force solution would simulate every single unit of time individually.

The idea is to process logs chronologically and determine which function is active during each timestamp. For every unit of execution time, we increment the currently executing function's counter.

To do this, we could:

• Parse all logs
• Maintain a stack of active functions
• Iterate timestamp by timestamp
• Attribute each time unit to the function currently at the top of the stack

This approach works because the CPU executes exactly one function at every timestamp. By simulating the timeline directly, we can accurately count exclusive execution time.

However, this approach becomes inefficient when timestamps are very large. Since timestamps can be as large as 10^9, iterating through every individual time unit is not feasible.

Optimal Stack-Based Approach

The key observation is that we do not need to simulate every unit of time individually. Instead, we only need to track transitions between events.

Between two consecutive log timestamps, the currently running function remains unchanged. Therefore, we can compute time intervals in chunks rather than step by step.

A stack is the ideal data structure because function calls naturally follow last-in-first-out behavior:

• When a function starts, it pauses the current function and becomes active
• When a function ends, execution resumes in the previous function

We also maintain a previous_time variable to track where the last execution interval began.

When processing logs:

• A "start" event means the currently running function gets execution time up to the new timestamp
• An "end" event means the current function gets execution time through the end timestamp inclusively

This allows us to process the logs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(T)	O(n)	Simulates every timestamp individually, where T is the maximum timestamp range
Optimal	O(logs.length)	O(n)	Uses a stack and processes each log once

Algorithm Walkthrough

1. Initialize an answer array of size n filled with zeros.

This array stores the exclusive execution time for each function ID. 2. Create an empty stack.

The stack represents the current call stack of executing functions. The function at the top is the currently active function. 3. Initialize previous_time to 0.

This variable tracks the beginning of the current execution interval. 4. Process each log in order.

Each log is split into:

• function_id
• event_type
• timestamp

5. Handle "start" logs.

If a new function starts:

• The function currently at the top of the stack has been executing from previous_time up to timestamp - 1
• Add timestamp - previous_time to the currently running function
• Push the new function onto the stack
• Update previous_time = timestamp

6. Handle "end" logs.

If a function ends:

• The current function has been executing from previous_time through timestamp
• Add timestamp - previous_time + 1 to the current function
• Pop the function from the stack
• Set previous_time = timestamp + 1

The +1 adjustment is necessary because end timestamps are inclusive. 7. Continue until all logs are processed. 8. Return the result array.

Why it works

The algorithm maintains the invariant that the function at the top of the stack is always the currently executing function. Every time execution switches because of a start or end event, the algorithm calculates exactly how long the previously active function was running.

Since every interval between consecutive log events belongs entirely to one function, and every interval is counted exactly once, the resulting execution times are correct.

Python Solution

from typing import List

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        result = [0] * n
        stack = []
        previous_time = 0

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

            if event_type == "start":
                if stack:
                    result[stack[-1]] += timestamp - previous_time

                stack.append(function_id)
                previous_time = timestamp

            else:
                result[stack[-1]] += timestamp - previous_time + 1
                stack.pop()
                previous_time = timestamp + 1

        return result

The implementation begins by initializing the result array and the stack. The result array stores the exclusive execution time for each function, while the stack keeps track of currently active function calls.

Each log string is parsed using split(":"). This gives us the function ID, event type, and timestamp.

When encountering a "start" event, the currently running function, if one exists, receives execution time from previous_time up to the new timestamp. Then the new function is pushed onto the stack because it becomes the active function.

When encountering an "end" event, the function at the top of the stack receives execution time through the inclusive end timestamp. After updating the result, the function is removed from the stack, and execution resumes at timestamp + 1.

The previous_time variable is critical because it prevents double-counting execution intervals.

Go Solution

package main

import (
	"strconv"
	"strings"
)

func exclusiveTime(n int, logs []string) []int {
	result := make([]int, n)
	stack := []int{}
	previousTime := 0

	for _, log := range logs {
		parts := strings.Split(log, ":")

		functionID, _ := strconv.Atoi(parts[0])
		eventType := parts[1]
		timestamp, _ := strconv.Atoi(parts[2])

		if eventType == "start" {
			if len(stack) > 0 {
				result[stack[len(stack)-1]] += timestamp - previousTime
			}

			stack = append(stack, functionID)
			previousTime = timestamp

		} else {
			result[stack[len(stack)-1]] += timestamp - previousTime + 1

			stack = stack[:len(stack)-1]
			previousTime = timestamp + 1
		}
	}

	return result
}

The Go implementation closely mirrors the Python solution. Slices are used for both the result array and the stack.

Go requires explicit parsing using strconv.Atoi, and logs are split using strings.Split.

Stack operations are implemented with slice append and reslicing:

• Push: append(stack, value)
• Pop: stack[:len(stack)-1]

Go integers are sufficient because timestamps fit comfortably within standard integer ranges on LeetCode.

Worked Examples

Example 1

Input:

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

Initial state:

Variable	Value
result	[0, 0]
stack	[]
previous_time	0

Step-by-step trace

Log	Action	Stack	Result	previous_time
0:start:0	Push 0	[0]	[0,0]	0
1:start:2	Function 0 ran for 2 units	[0,1]	[2,0]	2
1:end:5	Function 1 ran for 4 units	[0]	[2,4]	6
0:end:6	Function 0 ran for 1 more unit	[]	[3,4]	7

Final answer:

[3, 4]

Example 2

Input:

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

Step-by-step trace

Log	Action	Stack	Result	previous_time
0:start:0	Push first call	[0]	[0]	0
0:start:2	Parent ran for 2 units	[0,0]	[2]	2
0:end:5	Child ran for 4 units	[0]	[6]	6
0:start:6	Resume then recurse again	[0,0]	[6]	6
0:end:6	Second child ran for 1 unit	[0]	[7]	7
0:end:7	Parent ran for final 1 unit	[]	[8]	8

Final answer:

[8]

Example 3

Input:

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

Step-by-step trace

Log	Action	Stack	Result	previous_time
0:start:0	Push 0	[0]	[0,0]	0
0:start:2	Parent gets 2 units	[0,0]	[2,0]	2
0:end:5	Child gets 4 units	[0]	[6,0]	6
1:start:6	Function 1 starts immediately	[0,1]	[6,0]	6
1:end:6	Function 1 gets 1 unit	[0]	[6,1]	7
0:end:7	Function 0 gets final unit	[]	[7,1]	8

Final answer:

[7, 1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(logs.length)	Each log is processed exactly once
Space	O(n)	Stack depth can grow up to the number of active calls

The algorithm processes every log entry once and performs only constant-time work per log. Stack operations such as push and pop are O(1).

The stack stores active function calls. In the worst case, every function call is nested, so the stack size can grow proportional to the number of active calls.

Test Cases

from typing import List

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        result = [0] * n
        stack = []
        previous_time = 0

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

            if event_type == "start":
                if stack:
                    result[stack[-1]] += timestamp - previous_time

                stack.append(function_id)
                previous_time = timestamp

            else:
                result[stack[-1]] += timestamp - previous_time + 1
                stack.pop()
                previous_time = timestamp + 1

        return result

solution = Solution()

assert solution.exclusiveTime(
    2,
    ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
) == [3, 4]  # Basic nested call example

assert solution.exclusiveTime(
    1,
    ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]
) == [8]  # Recursive calls

assert solution.exclusiveTime(
    2,
    ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]
) == [7, 1]  # Mixed recursion and sibling call

assert solution.exclusiveTime(
    1,
    ["0:start:0", "0:end:0"]
) == [1]  # Single function executing for one timestamp

assert solution.exclusiveTime(
    2,
    ["0:start:0", "1:start:1", "1:end:1", "0:end:2"]
) == [2, 1]  # Child function executes for exactly one unit

assert solution.exclusiveTime(
    3,
    [
        "0:start:0",
        "1:start:2",
        "2:start:3",
        "2:end:4",
        "1:end:5",
        "0:end:6"
    ]
) == [3, 2, 2]  # Deeply nested calls

assert solution.exclusiveTime(
    1,
    ["0:start:0", "0:start:1", "0:end:1", "0:end:2"]
) == [3]  # Immediate recursive return

assert solution.exclusiveTime(
    2,
    ["0:start:0", "0:end:1", "1:start:2", "1:end:3"]
) == [2, 2]  # Sequential non-overlapping functions

Test	Why
Basic nested calls	Validates standard parent-child execution
Recursive calls	Ensures recursion is handled correctly
Mixed recursion and sibling calls	Tests multiple execution transitions
Single timestamp execution	Verifies inclusive end timestamp logic
One-unit child call	Tests minimal child execution duration
Deep nesting	Validates multi-level stack behavior
Immediate recursive return	Checks edge timing correctness
Sequential independent calls	Ensures functions can execute independently

Edge Cases

Recursive Function Calls

Recursive calls are one of the most important edge cases because the same function ID may appear multiple times simultaneously in the call stack. A naive implementation that only tracks whether a function is active would fail here.

The stack-based approach handles recursion naturally because each function call instance is pushed separately onto the stack. Even if the function ID is identical, each invocation has its own execution interval.

Inclusive End Timestamps

A common source of bugs is forgetting that end timestamps are inclusive.

For example:

0:start:5
0:end:5

This function executes for one full unit of time, not zero.

The implementation handles this correctly using:

timestamp - previous_time + 1

The +1 ensures the ending timestamp itself is counted.

Parent Function Resumption

After a child function finishes, the parent resumes execution immediately after the child's end timestamp.

This can easily cause double-counting if previous_time is not updated correctly.

For example:

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

After function 1 ends at time 5, function 0 resumes at time 6.

The implementation correctly sets:

previous_time = timestamp + 1

This guarantees the resumed execution begins at the correct next timestamp.