Leetcode 636. Exclusive Time of Functions
Problem
The problem describes a single threaded CPU that executes several functions. Each function has a unique ID between 0 and N-1. The CPU keeps a log to track when a function starts and ends. Each log entry is a string formatted as: "{function_id}:{start or end}:{timestamp}". For example, "0:start:3" indicates that the function with ID 0 started at the beginning of timestamp 3 while "1:end:2" means function with ID 1 ended at the end of timestamp 2.
Each function's exclusive time is defined as the number of time units spent in that function. The CPU is single-threaded, which means only one function is being executed at a given time unit. The problem requires us to calculate and return the exclusive time of each function sorted by their function IDs.
Let's consider an example to understand the problem better:
n = 2 logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
In this example, function 0 starts at the beginning of time 0, functions for 2 units of time and finishes at time 1. Then function 1 starts at time 2, functions for 4 units of time and ends at time 5. Function 0 resumes at time 6 and ends at time 6, meaning it functions for 1 unit of time. Therefore, function 0 spends a total of 3 units of time (2+1) while function 1 spends 4 units of time.
So, the output for this example will be [3, 4]
Approach
The solution approach involves the use of a stack data structure. The stack will store the IDs of the functions. We will iterate over the logs, and for each log entry, we will extract the function ID, label (start or end), and timestamp. If a function starts, we add the time that the last function was running to its exclusive time before pushing the current function into the stack. If a function ends, we pop the function from the stack and add its running time to its exclusive time.
Solution
This approach is based on the property of stack that it follows LIFO (Last In First Out) order which matches how function calls are handled in a single threaded CPU.
Since this problem involves deep understanding of the steps of single threaded CPU function execution, using some simple illustration will be helpful.
Let's demonstrate with an example: n = 2 logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Initial state: stack = [] ans = [0, 0] -- In the begining, no function has run, so all times are 0. prevTime = None -- No previous time as no function ran yet
For log "0:start:0": stack = [0] -- function 0 starts ans = [0, 0] -- Still no function has ended, so all times are 0. prevTime = 0 -- function 0 started at time 0
For log "1:start:2": stack = [0, 1] -- function 1 starts while function 0 was running ans = [2, 0] -- while function 1 starts, function 0 was paused. So, we update the time for function 0 (current time - previous time = 2 - 0). prevTime = 2 -- function 1 started at time 2
For log "1:end:5": stack = [0] -- function 1 ends ans = [2, 4] -- function 1 ended, so we calculate its exclusive time and add to its old time (current time + 1 - previous time = 5 + 1 -2). prevTime = 6 -- As function 1 ended at time 5, so next time we consider will be 6.
For log "0:end:6": stack = [] -- function 0 ends ans = [3, 4] -- function 0 ended, so we calculate its exclusive time and add to its old time (current time + 1 - previous time = 6 + 1 - 6). prevTime = 7 -- As function 0 ended at time 6, so next time we consider will be 7.
Finally, we get ans as [3, 4].
Python Solution
1 2python 3class Solution: 4 def exclusiveTime(self, n: int, logs: List[str]) -> List[int]: 5 ans = [0] * n 6 stack = [] 7 prev_time = 0 8 9 for log in logs: 10 parts = log.split(":") 11 id, label, timestamp = int(parts[0]), parts[1], int(parts[2]) 12 13 if label == 'start': 14 if stack: 15 ans[stack[-1]] += timestamp - prev_time 16 stack.append(id) 17 prev_time = timestamp 18 else: # label is 'end' 19 ans[stack.pop()] += timestamp - prev_time + 1 20 prev_time = timestamp + 1 21 22 return ans
Java Solution
1 2java 3class Solution { 4 public int[] exclusiveTime(int n, List<String> logs) { 5 int[] ans = new int[n]; 6 Stack<Integer> stack = new Stack<>(); 7 int prevTime = 0; 8 9 for (String log : logs) { 10 String[] parts = log.split(":"); 11 int id = Integer.parseInt(parts[0]); 12 String label = parts[1]; 13 int timestamp = Integer.parseInt(parts[2]); 14 15 if (label.equals("start")) { 16 if (!stack.empty()) { 17 ans[stack.peek()] += timestamp - prevTime; 18 } 19 stack.push(id); 20 prevTime = timestamp; 21 } else { // label is 'end' 22 ans[stack.pop()] += timestamp - prevTime + 1; 23 prevTime = timestamp + 1; 24 } 25 } 26 27 return ans; 28 } 29}
JavaScript Solution
1 2JavaScript 3var exclusiveTime = function(n, logs) { 4 let ans = new Array(n).fill(0); 5 let stack = []; 6 let prevTime = 0; 7 8 for (let log of logs) { 9 let parts = log.split(":"); 10 let id = parseInt(parts[0]); 11 let label = parts[1]; 12 let timestamp = parseInt(parts[2]); 13 14 if (label === 'start') { 15 if (stack.length > 0) { 16 ans[stack[stack.length-1]] += timestamp - prevTime; 17 } 18 stack.push(id); 19 prevTime = timestamp 20 } else { // label is 'end' 21 ans[stack.pop()] += timestamp - prevTime + 1; 22 prevTime = timestamp + 1; 23 } 24 } 25 26 return ans; 27};
C++ Solution
1
2cpp
3class Solution {
4public:
5 vector<int> exclusiveTime(int n, vector<string>& logs) {
6 vector<int> ans(n);
7 stack<int> stack;
8 int prevTime = 0;
9
10 for (string log : logs) {
11 size_t colon1 = log.find(":");
12 size_t colon2 = log.rfind(":");
13 int id = stoi(log.substr(0, colon1));
14 string label = log.substr(colon1 + 1, colon2 - colon1 - 1);
15 int timestamp = stoi(log.substr(colon2 + 1));
16
17 if (label == "start") {
18 if (!stack.empty())
19 ans[stack.top()] += timestamp - prevTime;
20 stack.push(id);
21 prevTime = timestamp;
22 } else { // label is 'end'
23 ans[stack.top()] += timestamp - prevTime + 1;
24 stack.pop();
25 prevTime = timestamp + 1;
26 }
27 }
28
29 return ans;
30 }
31};
C# Solution
1 2csharp 3public class Solution { 4 public int[] ExclusiveTime(int n, IList<string> logs) { 5 int[] ans = new int[n]; 6 Stack<int> stack = new Stack<int>(); 7 int prevTime = 0; 8 9 foreach(string log in logs){ 10 string[] parts = log.Split(":"); 11 int id = Int32.Parse(parts[0]); 12 string label = parts[1]; 13 int timestamp = Int32.Parse(parts[2]); 14 15 if (label == "start") { 16 if (stack.Count > 0) 17 ans[stack.Peek()] += timestamp - prevTime; 18 stack.Push(id); 19 prevTime = timestamp; 20 } else { // label is 'end' 21 ans[stack.Pop()] += timestamp - prevTime + 1; 22 prevTime = timestamp + 1; 23 } 24 } 25 26 return ans; 27 } 28}
In all solutions, note that if a function ends, we are considering timestamp + 1 as prevTime because when a function ends at a time t, so next should start at t + 1.### Kotlin Solution
1
2kotlin
3class Solution {
4 fun exclusiveTime(n: Int, logs: List<String>): IntArray {
5 val ans = IntArray(n)
6 val stack: Stack<Int> = Stack()
7 var prevTime = 0
8
9 for (log in logs) {
10 val parts: List<String> = log.split(":")
11 val id: Int = parts[0].toInt()
12 val label: String = parts[1]
13 val timestamp: Int = parts[2].toInt()
14
15 if(label == "start") {
16 if(!stack.empty()) {
17 ans[stack.peek()] += timestamp - prevTime
18 }
19 stack.push(id)
20 prevTime = timestamp
21 } else { // label is 'end'
22 ans[stack.pop()] += timestamp - prevTime + 1
23 prevTime = timestamp + 1
24 }
25 }
26
27 return ans
28 }
29}
Swift Solution
1 2swift 3class Solution { 4 func exclusiveTime(_ n: Int, _ logs: [String]) -> [Int] { 5 var ans = Array(repeating: 0, count: n) 6 var stack: [Int] = [] 7 var prevTime = 0 8 9 for log in logs { 10 let parts = log.split(separator: ":") 11 let id = Int(parts[0])! 12 let label = String(parts[1]) 13 let timestamp = Int(parts[2])! 14 15 if label == "start" { 16 if !stack.isEmpty { 17 ans[stack.last!] += timestamp - prevTime 18 } 19 stack.append(id) 20 prevTime = timestamp 21 } else { // label is 'end' 22 ans[stack.removeLast()] += timestamp - prevTime + 1 23 prevTime = timestamp + 1 24 } 25 } 26 27 return ans 28 } 29}
Go Solution
1 2go 3func exclusiveTime(n int, logs []string) []int { 4 ans := make([]int, n) 5 stack := make([]int, 0) 6 prevTime := 0 7 8 for _, log := range logs { 9 parts := strings.Split(log, ":") 10 id, _ := strconv.Atoi(parts[0]) 11 label := parts[1] 12 timestamp, _ := strconv.Atoi(parts[2]) 13 14 if label == "start" { 15 if len(stack) > 0 { 16 ans[stack[len(stack)-1]] += timestamp - prevTime 17 } 18 stack = append(stack, id) 19 prevTime = timestamp 20 } else { // label is 'end' 21 ans[stack[len(stack)-1]] += timestamp - prevTime + 1 22 stack = stack[:len(stack)-1] 23 prevTime = timestamp + 1 24 } 25 } 26 27 return ans 28}
Rust Solution
1
2rust
3impl Solution {
4 pub fn exclusive_time(n: i32, logs: Vec<String>) -> Vec<i32> {
5 let mut ans = vec![0; n as usize];
6 let mut stack: Vec<usize> = Vec::new();
7 let mut prev_time = 0;
8
9 for log in &logs {
10 let parts: Vec<&str> = log.split(":").collect();
11 let id: usize = parts[0].parse().unwrap();
12 let label: &str = parts[1];
13 let timestamp: i32 = parts[2].parse().unwrap();
14
15 if label == "start" {
16 if let Some(last) = stack.last() {
17 ans[*last] += timestamp - prev_time;
18 }
19 stack.push(id);
20 prev_time = timestamp;
21 } else { // label is 'end'
22 ans[stack.pop().unwrap()] += timestamp - prev_time + 1;
23 prevTime = timestamp + 1;
24 }
25 }
26
27 ans
28 }
29}
The main idea in all these solutions is to keep track of the execution of the function using a stack. We use a stack to handle the nested function calls, and use an auxiliary array to record the execution time of each function.
This problem might seem complex initially as it involves understanding the function execution in a single-thread CPU and tracking that order efficiently using data structures like stack. However, once we understand the stack operations and how the function calls correspond to stack operations, it becomes clearer and easier to come up with the solution.
Remember, the functions in this problem are not necessarily called in the order of their IDs, so we need a way to track the execution time for each function separately, regardless of the order in which they are called. That's why we are storing their IDs in a stack and their execution time in an additional data structure, typically an array or list.
The time complexity of this solution is O(n) where n is the number of logs. This is because we are iterating through the logs once. The space complexity is also O(n) where n is the number of logs. This is because in the worst case scenario where all function logs are "start", all function ids will be stored in the stack.
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.