Exclusive Time of Functions — Call Stack Simulation (LeetCode 636)

Exclusive Time of Functions (LeetCode 636) simulates what a CPU profiler does — track how long each function runs, excluding time spent in child functions. The stack naturally models the call stack.

The Problem

You have n functions (numbered 0 to n-1) on a single-threaded CPU. You are given a list of logs in the format "function_id:start_or_end:timestamp". Return an array where result[i] is the exclusive time of function i.

Exclusive time means the time a function spends executing its own code, not counting time spent in functions it calls.

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

Timeline:
t=0    t=1         t=4    t=5    t=6
|--fn0--|----fn1----|------fn0----|
   1         4            2

Result: [3, 4]
fn 0 ran during [0,0] and [5,6] → 1 + 2 = 3
fn 1 ran during [1,4] → 4

Important: “end” timestamps are inclusive — end:4 means the function occupied time unit 4, so the next available time is 5.

The Stack Approach

The idea is to simulate the call stack:

1. Maintain a stack of function IDs (currently running functions)
2. Track prev_time — the start of the current time segment
3. On start: charge elapsed time to the function currently on top, then push the new function
4. On end: charge elapsed time to the function being ended (top of stack), then pop it

Python Implementation

def exclusive_time(n, logs):
    """
    Simulate a call stack to compute exclusive time.
    Time: O(L) where L = number of log entries.
    Space: O(n) for result + O(depth) for stack.
    """
    result = [0] * n
    stack = []  # function IDs
    prev_time = 0

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

        if action == 'start':
            if stack:
                # Charge elapsed time to the function currently running
                result[stack[-1]] += timestamp - prev_time
            stack.append(fn_id)
            prev_time = timestamp
        else:  # end
            # Charge elapsed time to the ending function (inclusive)
            result[stack[-1]] += timestamp - prev_time + 1
            stack.pop()
            prev_time = timestamp + 1  # next available time unit

    return result

Detailed Trace

Let us trace n=2, logs=["0:start:0", "1:start:1", "1:end:4", "0:end:6"]:

Initial: result=[0,0], stack=[], prev_time=0

Log "0:start:0":
  action=start, fn=0, time=0
  stack is empty, no charge
  push 0                    stack=[0], prev_time=0

Log "1:start:1":
  action=start, fn=1, time=1
  stack top = 0
  result[0] += 1 - 0 = 1   result=[1,0]
  push 1                    stack=[0,1], prev_time=1

Log "1:end:4":
  action=end, fn=1, time=4
  stack top = 1
  result[1] += 4 - 1 + 1 = 4   result=[1,4]
  pop 1                    stack=[0], prev_time=5

Log "0:end:6":
  action=end, fn=0, time=6
  stack top = 0
  result[0] += 6 - 5 + 1 = 2   result=[3,4]
  pop 0                    stack=[], prev_time=7

Final: [3, 4] ✓

Handling Recursive Functions

A function can call itself. The stack handles this naturally because we push the same function ID again.

n = 1
logs = ["0:start:0", "0:start:2", "0:end:3", "0:end:4"]

Log "0:start:0": push 0, prev=0          stack=[0]
Log "0:start:2": result[0]+=2, push 0    stack=[0,0], result=[2]
Log "0:end:3":   result[0]+=2, pop       stack=[0], result=[4]
Log "0:end:4":   result[0]+=1, pop       stack=[], result=[5]

Answer: [5] — fn 0 owns all 5 time units.

A More Complex Example

n = 3
logs = [
    "0:start:0",
    "1:start:2",
    "2:start:3",
    "2:end:4",
    "1:end:5",
    "0:end:8"
]

Trace:

"0:start:0": push 0                     stack=[0], prev=0
"1:start:2": result[0]+=2, push 1       stack=[0,1], result=[2,0,0], prev=2
"2:start:3": result[1]+=1, push 2       stack=[0,1,2], result=[2,1,0], prev=3
"2:end:4":   result[2]+=2, pop          stack=[0,1], result=[2,1,2], prev=5
"1:end:5":   result[1]+=1, pop          stack=[0], result=[2,2,2], prev=6
"0:end:8":   result[0]+=3, pop          stack=[], result=[5,2,2], prev=9

Result: [5, 2, 2]
fn 0: [0,1] + [6,8] = 2 + 3 = 5
fn 1: [2,2] + [5,5] = 1 + 1 = 2
fn 2: [3,4] = 2
Total = 5 + 2 + 2 = 9 time units ✓

The +1 Trick for End Timestamps

The trickiest part is handling the inclusive end. When a log says end:4, that means time unit 4 is consumed. So:

• Duration for an end = timestamp - prev_time + 1
• After an end, prev_time = timestamp + 1

If you forget the +1, you will double-count or miss time units.

Edge Cases

1. Single function — ["0:start:0", "0:end:0"] → [1] (one time unit)
2. Recursive calls — same function ID pushed multiple times
3. Back-to-back starts — function starts immediately when previous one pauses
4. Large timestamps — no issue since we only compute differences
5. Many nested calls — stack depth can equal number of logs / 2

Complexity Analysis

Metric	Value
Time	O(L) where L is the number of log entries
Space	O(n + D) — result array of size n, stack depth D

When to Use This Pattern

Use call-stack simulation when:

• You need to track exclusive vs inclusive time for nested operations
• Logs have start/end events that nest like function calls
• You are building a profiler, tracer, or execution analyzer
• The problem involves nested intervals with ownership

Related Problems

Problem	Difficulty	Key Idea
LeetCode 636 — Exclusive Time of Functions	Medium	This problem
LeetCode 735 — Asteroid Collision	Medium	Stack simulation
LeetCode 853 — Car Fleet	Medium	Stack-based timeline
LeetCode 1249 — Min Remove to Make Valid Parentheses	Medium	Stack with indices

Key Takeaway

Exclusive Time of Functions is really about simulating a call stack. The stack tracks which function is currently running, and prev_time tracks when the current segment started. The key detail is handling inclusive end timestamps with the +1 adjustment.