Exclusive Time Of Functions - Leetcode Solution

The Exclusive Time Of Functions problem on LeetCode is a problem that involves simulating the execution of a list of tasks on a single processor. Each task is represented as a string in the form of "function_id:start_or_end:timestamp". The function_id is a positive integer that represents the function being executed, and the start_or_end is either "start" or "end", indicating whether the task is the start or end of the function's execution. The timestamp is a non-negative integer that represents the exact time when the task occurred.

The problem statement asks us to return an array of integers where the i-th element represents the exclusive amount of time that function i was running, i.e., the amount of time that function i was actively running, not including the time spent in other functions. It's important to note that the tasks are ordered by their timestamps, so we can assume that no two tasks will have the same timestamps.

To solve this problem, we can use a stack to keep track of the functions that are currently executing. We can iterate through the list of tasks and perform the following steps for each task:

1. Parse the function_id, start_or_end, and timestamp from the task string.
2. If the task is a function start, push the function_id onto the stack and record the start time in a dictionary that maps function_id to start time.
3. If the task is a function end, first pop the function_id from the stack (assuming it matches the current function_id), calculate the exclusive time by subtracting the current timestamp from the start time (recorded in the dictionary), and add this time to the exclusive time of the function_id. If the stack is not empty, update the start time of the previous function on the stack to exclude the time spent in this function.
4. Return the exclusive time array.

Here's the implementation of the above algorithm in Python:

def exclusiveTime(n: int, logs: List[str]) -> List[int]:
    exclusive_times = [0] * n
    stack = []
    prev_time = 0
    for log in logs:
        function_id, start_or_end, timestamp = log.split(':')
        function_id = int(function_id)
        timestamp = int(timestamp)
        if start_or_end == 'start':
            if stack:
                exclusive_times[stack[-1]] += timestamp - prev_time
            stack.append(function_id)
            prev_time = timestamp
        else:
            end_time = timestamp + 1
            exclusive_times[stack.pop()] += end_time - prev_time
            prev_time = end_time
    return exclusive_times

The time complexity of this algorithm is O(N), where N is the number of tasks in the logs list. The space complexity is O(N) as well, due to the stack and dictionary used to keep track of the execution times.

1