Last updated on February 2nd, 2025 at 05:18 am
Here, we see the Exclusive Time of Functions LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Stack
Companies
Facebook, Uber
Level of Question
Medium
Exclusive Time of Functions LeetCode Solution
Table of Contents
1. Problem Statement
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 a call 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 the exclusive time of each function in an array, where the value at the ith index represents the exclusive time for the function with ID i.
Example 1:
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:
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:
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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Stack-based Processing”. This pattern is commonly used to solve problems where you need to process nested or hierarchical structures, such as function calls, parentheses, or logs, in a Last-In-First-Out (LIFO) manner. In this problem, the stack is used to track the currently active function calls and calculate their exclusive execution times.
3. Code Implementation in Different Languages
3.1 Exclusive Time of Functions C++
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> ans(n);
stack<pair<int,int>> cur;
int prevTime = 0;
for (auto& s : logs){
int num = stoi(s.substr(0, s.find(':')));
int time = stoi(s.substr(s.rfind(':') + 1));
if (s.find('e') != -1){
ans[num] += time - prevTime + 1;
cur.pop();
prevTime = time + 1;
}
else{
if (!cur.empty()) ans[cur.top().first] += time - prevTime ;
cur.push({num, time});
prevTime = time;
}
}
return ans;
}
};
3.2 Exclusive Time of Functions Java
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] result = new int[n];
if (n == 0 || logs == null || logs.size() == 0) {
return result;
}
Deque<Integer> stack = new ArrayDeque<>();
int prevTime = 0;
for (String log : logs) {
String[] logParts = log.split(":");
int curTime = Integer.parseInt(logParts[2]);
if ("start".equals(logParts[1])) {
if (!stack.isEmpty()) {
result[stack.peek()] += curTime - prevTime;
}
stack.push(Integer.parseInt(logParts[0]));
prevTime = curTime;
} else {
result[stack.pop()] += curTime - prevTime + 1;
prevTime = curTime + 1;
}
}
return result;
}
}
3.3 Exclusive Time of Functions JavaScript
var exclusiveTime = function(n, logs) {
const sums = new Array(n).fill(0);
const stack = [];
let prevTime;
logs.forEach(log => {
const details = log.split(':');
const id = parseInt(details[0]);
const point = details[1];
const time = parseInt(details[2]);
if (point === 'start') {
if (stack.length > 0) {
let prevFn = stack[stack.length - 1];
sums[prevFn] += (time - prevTime);
}
stack.push(id);
prevTime = time;
} else {
const last = stack.pop();
sums[last] += (time - prevTime + 1);
prevTime = time + 1;
}
});
return sums;
};
3.4 Exclusive Time of Functions Python
class Solution(object):
def exclusiveTime(self, n, logs):
helper = lambda log: (int(log[0]), log[1], int(log[2]))
logs = [helper(log.split(':')) for log in logs]
ans, s = [0] * n, []
for (i, status, timestamp) in logs:
if status == 'start':
if s: ans[s[-1][0]] += timestamp - s[-1][1]
s.append([i, timestamp])
else:
ans[i] += timestamp - s.pop()[1] + 1
if s: s[-1][1] = timestamp+1
return ans
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(L) | O(N) |
| Java | O(L) | O(N) |
| JavaScript | O(L) | O(N) |
| Python | O(L) | O(N) |
where, L is the number of logs, and N is the number of functions.