Problem

On a single-threaded CPU, we execute a program containing n functions. Each function has a unique ID between 0 and n-1.

Function calls are stored in acall stack: when a function call starts, its ID is pushed onto the stack, and when a function call ends, its ID is popped off the stack. The function whose ID is at the top of the stack is the current function being executed. Each time a function starts or ends, we write a log with the ID, whether it started or ended, and the timestamp.

You are given a list logs, where logs[i] represents the ith log message formatted as a string "{function_id}:{"start" | "end"}:{timestamp}". For example, "0:start:3" means a function call with function ID 0 started at the beginning of timestamp 3, and "1:end:2" means a function call with function ID 1 ended at the end of timestamp 2. Note that a function can be called multiple times, possibly recursively.

A function’s exclusive time is the sum of execution times for all function calls in the program. For example, if a function is called twice, one call executing for 2 time units and another call executing for 1 time unit, the exclusive time is 2 + 1 = 3.

Return _theexclusive time of each function in an array, where the value at the _ith index represents the exclusive time for the function with IDi.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2019/04/05/diag1b.png)

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]
Explanation:
Function 0 starts at the beginning of time 0, then it executes 2 for units of time and reaches the end of time 1.
Function 1 starts at the beginning of time 2, executes for 4 units of time, and ends at the end of time 5.
Function 0 resumes execution at the beginning of time 6 and executes for 1 unit of time.
So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.

Example 2

1
2
3
4
5
6
7
8
9

Input: n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
Output: [8]
Explanation:
Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.
Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.
Function 0 (initial call) resumes execution then immediately calls itself again.
Function 0 (2nd recursive call) starts at the beginning of time 6 and executes for 1 unit of time.
Function 0 (initial call) resumes execution at the beginning of time 7 and executes for 1 unit of time.
So function 0 spends 2 + 4 + 1 + 1 = 8 units of total time executing.

Example 3

1
2
3
4
5
6
7
8
9

Input: n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
Output: [7,1]
Explanation:
Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.
Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.
Function 0 (initial call) resumes execution then immediately calls function 1.
Function 1 starts at the beginning of time 6, executes 1 unit of time, and ends at the end of time 6.
Function 0 resumes execution at the beginning of time 6 and executes for 2 units of time.
So function 0 spends 2 + 4 + 1 = 7 units of total time executing, and function 1 spends 1 unit of total time executing.

Constraints

  • 1 <= n <= 100
  • 1 <= logs.length <= 500
  • 0 <= function_id < n
  • 0 <= timestamp <= 10^9
  • No two start events will happen at the same timestamp.
  • No two end events will happen at the same timestamp.
  • Each function has an "end" log for each "start" log.

Solution

Method 1 – Stack Simulation

Intuition

We use a stack to simulate the function call stack. For each log, we update the exclusive time for the function at the top of the stack. When a function starts, we push it onto the stack. When it ends, we pop it and update its exclusive time, making sure to account for nested calls.

Approach

  1. Initialize an array ans of size n to store exclusive times.
  2. Use a stack to keep track of the function call stack.
  3. Track the previous timestamp (prev_time).
  4. For each log:
    • Parse the function id, type (start/end), and timestamp.
    • If it’s a start log:
      • If the stack is not empty, add the time since prev_time to the function at the top of the stack.
      • Push the new function id onto the stack.
      • Update prev_time to the current timestamp.
    • If it’s an end log:
      • Pop the function id from the stack.
      • Add the time from prev_time to the current timestamp (inclusive) to its exclusive time.
      • Update prev_time to timestamp + 1.
  5. Return the ans array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> ans(n, 0);
        stack<int> st;
        int prev = 0;
        for (auto& log : logs) {
            int p1 = log.find(':'), p2 = log.rfind(':');
            int id = stoi(log.substr(0, p1));
            string typ = log.substr(p1+1, p2-p1-1);
            int t = stoi(log.substr(p2+1));
            if (typ == "start") {
                if (!st.empty()) ans[st.top()] += t - prev;
                st.push(id);
                prev = t;
            } else {
                ans[st.top()] += t - prev + 1;
                st.pop();
                prev = t + 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func exclusiveTime(n int, logs []string) []int {
    ans := make([]int, n)
    st := []int{}
    prev := 0
    for _, log := range logs {
        parts := strings.Split(log, ":")
        id, _ := strconv.Atoi(parts[0])
        typ := parts[1]
        t, _ := strconv.Atoi(parts[2])
        if typ == "start" {
            if len(st) > 0 {
                ans[st[len(st)-1]] += t - prev
            }
            st = append(st, id)
            prev = t
        } else {
            ans[st[len(st)-1]] += t - prev + 1
            st = st[:len(st)-1]
            prev = t + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        int prev = 0;
        for (String log : logs) {
            String[] parts = log.split(":");
            int id = Integer.parseInt(parts[0]);
            String typ = parts[1];
            int t = Integer.parseInt(parts[2]);
            if (typ.equals("start")) {
                if (!st.isEmpty()) ans[st.peek()] += t - prev;
                st.push(id);
                prev = t;
            } else {
                ans[st.peek()] += t - prev + 1;
                st.pop();
                prev = t + 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun exclusiveTime(n: Int, logs: List<String>): IntArray {
        val ans = IntArray(n)
        val st = ArrayDeque<Int>()
        var prev = 0
        for (log in logs) {
            val parts = log.split(":")
            val id = parts[0].toInt()
            val typ = parts[1]
            val t = parts[2].toInt()
            if (typ == "start") {
                if (st.isNotEmpty()) ans[st.last()] += t - prev
                st.addLast(id)
                prev = t
            } else {
                ans[st.last()] += t - prev + 1
                st.removeLast()
                prev = t + 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:
        ans = [0] * n
        st = []
        prev = 0
        for log in logs:
            fid, typ, t = log.split(":")
            fid, t = int(fid), int(t)
            if typ == "start":
                if st:
                    ans[st[-1]] += t - prev
                st.append(fid)
                prev = t
            else:
                ans[st[-1]] += t - prev + 1
                st.pop()
                prev = t + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn exclusive_time(n: i32, logs: Vec<String>) -> Vec<i32> {
        let mut ans = vec![0; n as usize];
        let mut st = vec![];
        let mut prev = 0;
        for log in logs {
            let parts: Vec<&str> = log.split(':').collect();
            let id = parts[0].parse::<usize>().unwrap();
            let typ = parts[1];
            let t = parts[2].parse::<i32>().unwrap();
            if typ == "start" {
                if let Some(&top) = st.last() {
                    ans[top] += t - prev;
                }
                st.push(id);
                prev = t;
            } else {
                ans[*st.last().unwrap()] += t - prev + 1;
                st.pop();
                prev = t + 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    exclusiveTime(n: number, logs: string[]): number[] {
        const ans = Array(n).fill(0);
        const st: number[] = [];
        let prev = 0;
        for (const log of logs) {
            const [fid, typ, t] = log.split(":");
            const id = parseInt(fid), time = parseInt(t);
            if (typ === "start") {
                if (st.length) ans[st[st.length-1]] += time - prev;
                st.push(id);
                prev = time;
            } else {
                ans[st[st.length-1]] += time - prev + 1;
                st.pop();
                prev = time + 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m), where m is the number of logs.
  • 🧺 Space complexity: O(n + m), for the answer array and stack.