LeetCode 636: Exclusive Time of Functions Solution in Python – A Step-by-Step Guide

What Is LeetCode 636: Exclusive Time of Functions?

In LeetCode 636: Exclusive Time of Functions, you’re given an integer n (number of functions, 0 to n-1) and a list of logs in the format "function_id:action:timestamp", where action is "start" or "end", and timestamp is an integer. Your task is to compute the exclusive time each function runs—time spent executing without overlap from nested calls—and return an array of times for each function. For example, with logs ["0:start:0", "1:start:2", "1:end:5", "0:end:6"], function 0 runs exclusively from 0-2 and 5-6 (3 units), while function 1 runs from 2-5 (3 units). This problem tests your ability to manage overlapping intervals and track execution states.

Problem Statement

• Input:
• n: Integer (number of functions, 1 ≤ n ≤ 100).
• logs: List of strings "function_id:action:timestamp".
• Output: List of integers—exclusive time for each function.
• Rules:
• function_id: 0 to n-1.
• action: "start" or "end".
• timestamp: Non-negative integer, non-decreasing across logs.
• Compute time each function runs without nested overlap.

Constraints

• 1 ≤ n ≤ 100.
• 1 ≤ logs.length ≤ 500.
• 0 ≤ function_id < n.
• 0 ≤ timestamp ≤ 10⁹.
• Logs are sorted by timestamp (non-decreasing).

Examples

• Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
• Output: [3, 3] (Function 0: 0-2, 5-6; Function 1: 2-5)
• Input: n = 1, logs = ["0:start:0","0:end:7"]
• Output: [8] (Function 0: 0-7, inclusive)
• Input: n = 3, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
• Output: [7, 1, 0] (Function 0: 0-2, 5-7; Function 1: 6-6)

These examples set the timer—let’s solve it!

Understanding the Problem: Tracking Exclusive Time

To solve LeetCode 636: Exclusive Time of Functions in Python, we need to process a list of logs to calculate each function’s exclusive runtime, accounting for nested calls. A naive approach—computing all intervals and subtracting overlaps—could get messy with multiple nestings. Since logs are chronological, we can process them sequentially, tracking active functions. We’ll use:

• Best Solution (Stack-Based with Time Tracking): O(n) time, O(n) space—fast and intuitive (n = log entries).
• Alternative Solution (Interval-Based with Sorting): O(n log n) time, O(n) space—visual but slower.

Let’s start with the stack-based solution, breaking it down for beginners.

Best Solution: Stack-Based with Time Tracking

Why This Is the Best Solution

The stack-based approach with time tracking is the top choice for LeetCode 636 because it’s efficient—O(n) time with O(n) space—and naturally handles nested calls by using a stack to track active functions and timestamps. It processes logs in order, updating exclusive times incrementally, fitting constraints (500 logs, n ≤ 100) perfectly. It’s like watching a call stack in real-time, clocking each function’s solo run!

How It Works

Think of this as a function timer:

• Step 1: Initialize:
• Stack for active function IDs.
• Array times for exclusive time per function.
• prev_time to track last timestamp.
• Step 2: Process Logs:
• For each log:
• "start": Add time since last event to top function (if any), push new ID, update prev_time.
• "end": Add time to ending function, pop stack, update prev_time.
• Step 3: Compute Exclusive Time:
• Adjust parent function’s time by subtracting nested time.
• Step 4: Return Result:
• Return times array.

It’s like a runtime logger—stack and tick!

Step-by-Step Example

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

• Step 1: Init:
• Stack = [], times = [0, 0], prev_time = 0.
• Step 2: Process:
• "0:start:0":
• Stack = [0], prev_time = 0.
• "1:start:2":
• times[0] += 2 - 0 = 2 (0 runs 0-2).
• Stack = [0, 1], prev_time = 2.
• "1:end:5":
• times[1] += 5 - 2 = 3 (1 runs 2-5).
• Stack = [0], prev_time = 5.
• "0:end:6":
• times[0] += 6 - 5 = 1 (0 runs 5-6, total 3).
• Stack = [], prev_time = 6.
• Step 3: times = [3, 3].
• Output: [3, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        # Step 1: Initialize stack and times
        stack = []  # Active function IDs
        times = [0] * n  # Exclusive time per function
        prev_time = 0  # Last timestamp processed

        # Step 2: Process each log
        for log in logs:
            func_id, action, timestamp = log.split(":")
            func_id = int(func_id)
            timestamp = int(timestamp)

            if action == "start":
                # Add time to current top function (if any)
                if stack:
                    times[stack[-1]] += timestamp - prev_time
                stack.append(func_id)
                prev_time = timestamp
            else:  # "end"
                # Add time to ending function
                times[stack[-1]] += timestamp - prev_time + 1
                stack.pop()
                prev_time = timestamp + 1

        # Step 3: Return exclusive times
        return times

• Lines 4-6: Init: Empty stack, times array, prev_time.
• Lines 9-23: Process logs:
• Parse log into ID, action, timestamp.
• "start": Update parent time, push ID.
• "end": Update ending time (inclusive), pop, adjust prev_time.
• Time Complexity: O(n)—one pass through logs.
• Space Complexity: O(n)—stack size.

This is like a function stopwatch—track and tally!

Alternative Solution: Interval-Based with Sorting

Why an Alternative Approach?

The interval-based approach with sorting converts logs into start/end intervals—O(n log n) time, O(n) space. It’s more visual, sorting events to process chronologically, but slower due to sorting overhead. It’s like plotting function timelines and slicing them!

How It Works

Picture this as a timeline cutter:

• Step 1: Parse logs into events (start/end, time, ID).
• Step 2: Sort events by time, breaking ties with end before start.
• Step 3: Process events:
• Track active functions, update times at transitions.
• Step 4: Return times array.

It’s like a time slicer—sort and segment!

Step-by-Step Example

Example: Same as above

• Step 1: Events = [(0, "start", 0), (2, "start", 1), (5, "end", 1), (6, "end", 0)].
• Step 2: Sorted (end before start on ties).
• Step 3: Process:
• t=0, start 0: Active = [0], prev = 0.
• t=2, start 1: times[0] += 2-0 = 2, Active = [0, 1], prev = 2.
• t=5, end 1: times[1] += 5-2 = 3, Active = [0], prev = 5.
• t=6, end 0: times[0] += 6-5 = 1 (total 3), Active = [], prev = 6.
• Output: [3, 3].

Code for Interval Approach

Copy codeclass Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        # Step 1: Parse logs into events
        events = []
        for log in logs:
            func_id, action, timestamp = log.split(":")
            events.append((int(timestamp), action, int(func_id)))

        # Step 2: Sort events (end before start on ties)
        events.sort(key=lambda x: (x[0], x[1] == "start"))

        # Step 3: Process events
        stack = []
        times = [0] * n
        prev_time = 0

        for timestamp, action, func_id in events:
            if stack:
                times[stack[-1]] += timestamp - prev_time
            if action == "start":
                stack.append(func_id)
            else:
                stack.pop()
            prev_time = timestamp

        # Step 4: Return times
        return times

• Lines 6-9: Parse into (time, action, ID).
• Line 12: Sort by time, prioritize "end".
• Lines 15-23: Process:
• Update time for top function, manage stack.
• Time Complexity: O(n log n)—sorting.
• Space Complexity: O(n)—events and stack.

It’s a timeline tracker—visual but slower!

Comparing the Two Solutions

• Stack-Based (Best):
• Pros: O(n) time, O(n) space, fast and simple.
• Cons: Assumes log order (given).
• Interval-Based (Alternative):
• Pros: O(n log n) time, O(n) space, handles unsorted logs.
• Cons: Sorting overhead.

Stack-based wins for efficiency.

Additional Examples and Edge Cases

• Input: n = 1, ["0:start:0","0:end:0"]
• Output: [1].
• Input: n = 2, ["0:start:0","0:end:1","1:start:2","1:end:3"]
• Output: [2, 1].

Both handle these well.

Complexity Breakdown

• Stack-Based: Time O(n), Space O(n).
• Interval-Based: Time O(n log n), Space O(n).

Stack-based is optimal.

Key Takeaways

• Stack-Based: Real-time tracking—smart!
• Interval-Based: Sorted intervals—clear!
• Timing: Logs are fun.
• Python Tip: Stacks rock—see Python Basics.

Final Thoughts: Time Those Functions

LeetCode 636: Exclusive Time of Functions in Python is a neat timing challenge. Stack-based tracking offers speed and simplicity, while interval-based sorting provides a visual alternative. Want more? Try LeetCode 56: Merge Intervals or LeetCode 735: Asteroid Collision. Ready to clock? Head to Solve LeetCode 636 on LeetCode and measure those runtimes today!