Exclusive Time of Functions: Stack-Based Execution Tracking

May 20, 20265 min read

leetcodeproblemmediumarraysstacks

If you have ever used a profiler to figure out which function is eating all your CPU time, you already understand the core idea behind this problem. A profiler tracks when each function starts and stops, and it reports how much time each function spent running on its own, not counting time spent inside functions it called. That is exactly what LeetCode 636: Exclusive Time of Functions asks you to compute.

You are given n functions (numbered 0 through n-1) running on a single-threaded CPU. Each function can call another function, pausing its own execution until the called function returns. You receive a list of log entries recording when each function starts or ends, and you need to return an array where each entry is the total exclusive time for that function.

n=2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]. Function 0 runs at t=0..1 and t=6 (exclusive time 3). Function 1 runs at t=2..5 (exclusive time 4).

Why this problem matters

This problem tests your ability to simulate nested function calls using a stack. The same pattern appears in CPU scheduling simulations, recursive call tracing, and bracket-matching problems. If you can model "the currently running function" with a stack and track time intervals correctly, you can handle a whole family of similar problems.

It also reinforces a subtle but important detail: understanding the difference between inclusive and exclusive timestamps. The "end" timestamp in this problem is inclusive, meaning that if a function ends at time 5, it was still executing during time unit 5. Getting this off by one wrong is the most common bug.

The approach

The key insight is that only one function can be running at any given time (single-threaded CPU). When a new function starts, the currently running function pauses. When a function ends, the function underneath it on the call stack resumes.

A stack is the natural data structure here. You push a function ID when it starts and pop it when it ends. The trick is tracking how much time to credit to each function.

You keep a variable prev_time that records the last timestamp you processed. When you encounter a new log entry:

Start: The function on top of the stack has been running since prev_time. Credit it timestamp - prev_time units, then push the new function and update prev_time.
End: The function on top of the stack has been running since prev_time. Credit it timestamp - prev_time + 1 units (the +1 because end is inclusive), pop it, and set prev_time = timestamp + 1.

def exclusiveTime(n, logs):
    result = [0] * n
    stack = []
    prev_time = 0

    for log in logs:
        parts = log.split(":")
        func_id = int(parts[0])
        action = parts[1]
        timestamp = int(parts[2])

        if action == "start":
            if stack:
                result[stack[-1]] += timestamp - prev_time
            stack.append(func_id)
            prev_time = timestamp
        else:
            result[stack.pop()] += timestamp - prev_time + 1
            prev_time = timestamp + 1

    return result

The +1 on end timestamps is the detail that trips people up most. An end log at time 5 means the function was still executing during time unit 5. So the duration is end - prev_time + 1, and the next available time unit is end + 1. If you forget this, every exclusive time will be off by one.

Practice this problem with spaced repetition

Step-by-step walkthrough

Let's trace through the example: n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]. Watch how the stack tracks which function is currently active and how prev_time shifts after each log entry.

Step 1: Process "0:start:0"

Function 0 starts at time 0. Stack is empty so nothing to accumulate. Push 0. Set prev_time = 0.

Step 2: Process "1:start:2"

Function 1 starts at time 2. The top of stack is func 0, so add 2 - 0 = 2 to result[0]. Push 1. Set prev_time = 2.

Step 3: Process "1:end:5"

Function 1 ends at time 5. Pop func 1, add 5 - 2 + 1 = 4 to result[1]. Set prev_time = 5 + 1 = 6.

Step 4: Process "0:end:6"

Function 0 ends at time 6. Pop func 0, add 6 - 6 + 1 = 1 to result[0]. Final result: [3, 4].

Notice a few things from the walkthrough:

Start logs credit time to the paused function. When function 1 starts at time 2, function 0 has been running since time 0. We credit 2 units to function 0 before pushing function 1.
End logs credit time to the ending function. When function 1 ends at time 5, it has been running since time 2. We credit 5 - 2 + 1 = 4 units to function 1.
prev_time jumps past the end timestamp. After an end at time 5, prev_time becomes 6. This prevents double-counting that time unit.

Complexity analysis

	Time	Space
Stack solution	O(n)	O(n)

Time: O(n) where n is the number of log entries. We process each log entry exactly once with O(1) work per entry (splitting the string is bounded by the constant format).

Space: O(n) for the stack in the worst case. If every function calls another function before any of them return, the stack can grow to hold all n function IDs. The result array also takes O(n) space.

Build your pattern library with CodeBricks

Edge cases to watch for

Before submitting, verify your solution handles these:

Single function, one call. n=1, logs = ["0:start:0", "0:end:0"]. The exclusive time should be [1] (one time unit). This tests the +1 on end timestamps.
Recursive calls. A function can call itself. logs = ["0:start:0", "0:start:2", "0:end:3", "0:end:4"]. The stack will have function 0 twice. Each call gets its own exclusive time, and they all accumulate in result[0].
Back-to-back functions. logs = ["0:start:0", "0:end:2", "1:start:3", "1:end:5"]. No nesting, just sequential execution. The stack never has more than one element.
Deeply nested calls. Many functions calling each other in a chain before any return. The stack grows to its maximum depth, but the algorithm still processes each log in O(1).
Multiple calls to the same function. Function 0 could be called at different times. The result accumulates across all calls.

The building blocks

This problem is built on one core building block:

Stack-based interval tracking

The pattern of using a stack to track "what is currently active" while processing events in chronological order. When a new event starts, the previous active item pauses. When an event ends, the item underneath resumes.

This same structure appears in:

Basic Calculator: the stack tracks the current expression context, pausing it when you enter parentheses and resuming when you leave
Decode String (3[a2[bc]]): the stack tracks the current string being built, pausing when you enter a nested bracket
Task Scheduler: tracking which task is running and managing idle time between executions

The key to all of these is the same: push on "open" events, pop on "close" events, and track the accumulated value for the item on top of the stack.

From understanding to recall

You have seen how the stack tracks the currently running function and how prev_time handles the handoff between start and end events. The algorithm is compact, maybe 15 lines of real logic. But under time pressure, the details get fuzzy. Do you add +1 on start or end? Do you update prev_time before or after crediting time? Do you credit to stack[-1] or to the function in the log?

These are recall problems, not comprehension problems. You understand it now, but writing it from scratch in three weeks is a different skill. Spaced repetition closes that gap. You write the stack-based exclusive time tracker from memory at increasing intervals. Each repetition reinforces the +1 rule, the prev_time update order, and the credit-before-push pattern. After a few cycles, the code flows without hesitation.

Valid Parentheses - classic stack matching pattern
Daily Temperatures - stack-based tracking of paired events
Basic Calculator - stack for nested expression evaluation

Try CodeBricks free