Problem Description

You are given n functions with unique IDs from 0 to n-1. Each function can start or end at a specific timestamp. The function call logs are provided as a list of strings logs, where each log is formatted as "function_id:start_or_end:timestamp".

The logs are ordered by timestamp and represent a single-threaded CPU, so only one function runs at a time. Functions can call other functions (including recursion).

Your task is to return an array res where res[i] is the exclusive time of function i. The exclusive time is the total time spent executing function i itself, excluding the time spent in any other function called by i.

Constraints:

• 1 ≤ n ≤ 100
• 1 ≤ logs.length ≤ 10,000
• There is exactly one valid call stack at any time (no concurrency)

Thought Process

At first glance, it may seem that we can just sum up the time intervals for each function. However, because functions can call other functions (including themselves), we need to be careful not to double-count time spent in nested calls.

A brute-force approach might try to track all time intervals and subtract overlapping parts, but that quickly gets complicated and inefficient.

Instead, we notice that the problem is similar to simulating a call stack: when a function starts, it may pause the currently running function, and when it ends, execution returns to the previous function. This suggests using a stack data structure to keep track of which function is currently running and to manage nested calls.

Solution Approach

We simulate the execution using a stack and process each log entry in order:

1. Initialize:
   • An array res of size n to store exclusive times of each function, initialized to 0.
   • An empty stack to keep track of currently running function IDs.
   • A variable prev_time to track the previous timestamp.
2. Iterate through logs: For each log, parse the function_id, type ("start" or "end"), and timestamp.
3. On "start":
   • If the stack is not empty, the function on top of the stack has been running since prev_time until now. Add timestamp - prev_time to its exclusive time.
   • Push the new function ID onto the stack.
   • Update prev_time to the current timestamp.
4. On "end":
   • The function on top of the stack is ending. Add timestamp - prev_time + 1 to its exclusive time (the "+1" accounts for inclusive end timestamp).
   • Pop it from the stack.
   • Update prev_time to timestamp + 1 (the next time unit).
5. Continue until all logs are processed.

Example Walkthrough

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

Let's walk through each log:

• "0:start:0": Function 0 starts at time 0. Stack: [0]. prev_time = 0.
• "1:start:2": Function 1 starts at time 2.
  • Function 0 was running from 0 to 2 (2 units). Add 2 to res[0].
  • Stack: [0, 1]. prev_time = 2.
• "1:end:5": Function 1 ends at time 5.
  • Function 1 ran from 2 to 5 (inclusive), so 5 - 2 + 1 = 4 units. Add 4 to res[1].
  • Stack: [0]. prev_time = 6.
• "0:end:6": Function 0 ends at time 6.
  • Function 0 ran from 6 to 6 (inclusive), so 6 - 6 + 1 = 1 unit. Add 1 to res[0].
  • Stack: []. prev_time = 7.

Time and Space Complexity

Brute-force:

• Would require checking all intervals for overlap, resulting in O(n * m) time, where m is the number of logs.

• Time Complexity: O(m), where m is the number of logs, since each log is processed once.
• Space Complexity: O(n + m) for the result array and the stack (stack depth at most n).

Summary

The key insight is to model the execution as a stack of function calls, updating exclusive time only for the currently running function. This avoids double-counting and handles nesting and recursion naturally. The result is a clean, efficient O(m) solution that is both intuitive and robust for single-threaded function execution logs.

Code Implementation

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        res = [0] * n
        stack = []
        prev_time = 0
        for log in logs:
            fn_id, typ, time = log.split(":")
            fn_id = int(fn_id)
            time = int(time)
            if typ == "start":
                if stack:
                    res[stack[-1]] += time - prev_time
                stack.append(fn_id)
                prev_time = time
            else:
                res[stack.pop()] += time - prev_time + 1
                prev_time = time + 1
        return res
      

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n, 0);
        stack<int> st;
        int prev_time = 0;
        for (const string& log : logs) {
            int pos1 = log.find(':');
            int pos2 = log.rfind(':');
            int fn_id = stoi(log.substr(0, pos1));
            string typ = log.substr(pos1 + 1, pos2 - pos1 - 1);
            int time = stoi(log.substr(pos2 + 1));
            if (typ == "start") {
                if (!st.empty()) {
                    res[st.top()] += time - prev_time;
                }
                st.push(fn_id);
                prev_time = time;
            } else {
                res[st.top()] += time - prev_time + 1;
                st.pop();
                prev_time = time + 1;
            }
        }
        return res;
    }
};
      

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        int prevTime = 0;
        for (String log : logs) {
            String[] parts = log.split(":");
            int fnId = Integer.parseInt(parts[0]);
            String typ = parts[1];
            int time = Integer.parseInt(parts[2]);
            if (typ.equals("start")) {
                if (!stack.isEmpty()) {
                    res[stack.peek()] += time - prevTime;
                }
                stack.push(fnId);
                prevTime = time;
            } else {
                res[stack.pop()] += time - prevTime + 1;
                prevTime = time + 1;
            }
        }
        return res;
    }
}
      

var exclusiveTime = function(n, logs) {
    const res = new Array(n).fill(0);
    const stack = [];
    let prevTime = 0;
    for (const log of logs) {
        const [fnIdStr, typ, timeStr] = log.split(':');
        const fnId = parseInt(fnIdStr);
        const time = parseInt(timeStr);
        if (typ === "start") {
            if (stack.length) {
                res[stack[stack.length - 1]] += time - prevTime;
            }
            stack.push(fnId);
            prevTime = time;
        } else {
            res[stack.pop()] += time - prevTime + 1;
            prevTime = time + 1;
        }
    }
    return res;
};