Exclusive Time of Functions solution and explanation
IBM
Google
9 more videos on this problem
EXCLUSIVE TIME OF FUNCTIONS | LEETCODE 636 | PYTHON SOLUTIONCracking FAANG · 15:42 · 15K views
Exclusive Time Of Functions | Leetcode 636Pepcoding · 25:32 · 10K views
Exclusive Time of Functions (LeetCode 636 - Medium)TechMockInterview · 13:25 · 7K views
花花酱 LeetCode 636. Exclusive Time of Functions - 刷题找工作 EP166Hua Hua · 15:04 · 6K views
What is the catch? Leetcode 636 Exclusive Time of Functions | Stack | Java | Interview | SoftwareBharat Singh · 13:24 · 5K views
Exclusive Time of Functions || Leetcode 636 || 1 Variant that Big Tech AsksCoding with Minmer · 26:03 · 5K views
LeetCode 636. Exclusive Time of Functions Explanation and Solutionhappygirlzt · 7:58 · 4K views
Leetcode 636 Exclusive Time of FunctionsRen Zhang · 17:58 · 2K views
Leetcode - 636 . Exclusive Time of Functions | stackRaman Bhari · 19:38 · 1K views
636. Exclusive Time of Functions - English VersionSimple Code - 단순코드 · 7:20 · 1K views
The 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 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.
Constraints:
1 <= n <= 1001 <= logs.length <= 5000 <= function_id < n0 <= timestamp <= 109- 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.
Approach overview
Problem Overview: You receive execution logs for n functions running on a single-threaded CPU. Each log marks a function start or end with a timestamp. Because calls can be nested, a function may pause while another runs. The task is to compute the exclusive time for every function, meaning the total time spent running that function itself, excluding time spent in its child calls.
Approach 1: Stack-based Simulation (O(n) time, O(n) space)
This is the standard solution and models the call stack directly using a stack. Each time you encounter a start log, push the function ID onto the stack because it becomes the currently executing function. When an end log appears, pop from the stack and compute the duration using the stored start timestamp and the current timestamp. The key insight is tracking the previous timestamp. Whenever a new function starts, the currently running function accumulates time until that moment. When a function ends, add its inclusive interval and move the previous timestamp forward. Since each log is processed exactly once and each function enters and leaves the stack once, the runtime is O(n) with O(n) stack space in the worst case of deep nesting.
This approach works naturally because nested calls behave exactly like a function call stack in real programs. It avoids recomputation and cleanly separates execution windows for parent and child functions.
Approach 2: Using a List to Manage Active Calls (O(n) time, O(n) space)
Instead of a traditional stack data structure, you can maintain a list representing active calls. The last element in the list acts as the currently executing function. Each log entry is parsed and processed sequentially using simple array operations such as append and remove. When a start log appears, update the running function's accumulated time using the difference between the current timestamp and the previous timestamp, then append the new function to the list. When an end log appears, finalize the execution time for the function at the end of the list and remove it.
The algorithm behaves similarly to the stack solution but relies on list operations instead of explicit stack APIs. Each log is processed once, giving O(n) time complexity. The active call list grows with nesting depth, so space complexity remains O(n). This version is useful if you're implementing the logic in languages or environments where lists are more convenient than stacks.
Recommended for interviews: The stack-based approach is what interviewers expect. It mirrors the real execution stack of function calls and clearly demonstrates your understanding of nested execution and timestamp accounting. Walking through how you update the previous timestamp and subtract child execution time shows strong reasoning about state transitions. The list-based variation works the same way internally, but presenting the explicit stack model communicates the concept more clearly during interviews.
Approach 1: Stack-based Approach
This approach leverages a stack to track the active functions. When a function starts, push its ID and timestamp onto the stack. When a function ends, pop the top of the stack to calculate the exclusive time for that function by subtracting the start time from the end time. Adjust for any nested function calls by subtracting the exclusive time of the nested calls from the current function.
def exclusiveTime(n, logs):
result = [0] * n
stack = []
prevTime = 0
for log in logs:
id_str, typ, time_str = log.split(':')
id, time = int(id_str), int(time_str)
if typ == "start":
if stack:
result[stack[-1][0]] += time - prevTime
stack.append((id, time))
prevTime = time
else: # "end"
result[stack[-1][0]] += time - prevTime + 1
stack.pop()
prevTime = time + 1
return result
# Example usage
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
n = 2
print(exclusiveTime(n, logs)) # Output: [3, 4]import java.util.*;
public class ExclusiveTime {
public static int[] exclusiveTime(int n, List<String> logs) {
int[] result = new int[n];
Stack<int[]> stack = new Stack<>();
int prevTime = 0;
for (String log : logs) {
String[] parts = log.split(":");
int id = Integer.parseInt(parts[0]);
String type = parts[1];
int time = Integer.parseInt(parts[2]);
if (type.equals("start")) {
if (!stack.isEmpty()) {
result[stack.peek()[0]] += time - prevTime;
}
stack.push(new int[]{id, time});
prevTime = time;
} else { // "end"
result[stack.peek()[0]] += time - prevTime + 1;
stack.pop();
prevTime = time + 1;
}
}
return result;
}
public static void main(String[] args) {
List<String> logs = Arrays.asList("0:start:0","1:start:2","1:end:5","0:end:6");
int n = 2;
int[] result = exclusiveTime(n, logs);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> result(n, 0);
stack<pair<int, int>> st;
int prevTime = 0;
for (const string& log : logs) {
int pos1 = log.find(':');
int pos2 = log.find(':', pos1 + 1);
int id = stoi(log.substr(0, pos1));
string type = log.substr(pos1 + 1, pos2 - pos1 - 1);
int time = stoi(log.substr(pos2 + 1));
if (type == "start") {
if (!st.empty()) {
result[st.top().first] += time - prevTime;
}
st.push({id, time});
prevTime = time;
} else { // "end"
result[st.top().first] += time - prevTime + 1;
st.pop();
prevTime = time + 1;
}
}
return result;
}
int main() {
vector<string> logs = {"0:start:0","1:start:2","1:end:5","0:end:6"};
int n = 2;
vector<int> result = exclusiveTime(n, logs);
cout << "[";
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << (i == result.size() - 1 ? "" : ", ");
}
cout << "]\n";
return 0;
}function exclusiveTime(n, logs) {
let result = new Array(n).fill(0);
let stack = [];
let prevTime = 0;
logs.forEach(log => {
let [id, type, timestamp] = log.split(':');
id = parseInt(id);
timestamp = parseInt(timestamp);
if (type === 'start') {
if (stack.length !== 0) {
result[stack[stack.length - 1][0]] += timestamp - prevTime;
}
stack.push([id, timestamp]);
prevTime = timestamp;
} else { // "end"
result[stack.pop()[0]] += timestamp - prevTime + 1;
prevTime = timestamp + 1;
}
});
return result;
}
// Example usage
let logs = ["0:start:0","1:start:2","1:end:5","0:end:6"];
let n = 2;
console.log(exclusiveTime(n, logs)); // Output: [3, 4]#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_LOG_LEN 20
#define MAX_STACK_SIZE 100
#define DELIM ":"
typedef struct {
int id;
int time;
} StackNode;
StackNode stack[MAX_STACK_SIZE];
int top = -1;
void push(int id, int time) {
stack[++top] = (StackNode){id, time};
}
StackNode pop() {
return stack[top--];
}
int *exclusiveTime(int n, char **logs, int logsSize, int *returnSize) {
int *result = (int *)calloc(n, sizeof(int));
*returnSize = n;
int prevTime = 0;
for (int i = 0; i < logsSize; i++) {
int id, time;
char event[6];
char *log = strdup(logs[i]);
char *token = strtok(log, DELIM);
id = atoi(token);
token = strtok(NULL, DELIM);
strcpy(event, token);
token = strtok(NULL, DELIM);
time = atoi(token);
if (strcmp(event, "start") == 0) {
if (top != -1) {
result[stack[top].id] += time - prevTime;
}
push(id, time);
prevTime = time;
} else {
result[stack[top].id] += time - prevTime + 1;
pop();
prevTime = time + 1;
}
free(log);
}
return result;
}
int main() {
char *logs[] = {"0:start:0","1:start:2","1:end:5","0:end:6"};
int logsSize = sizeof(logs) / sizeof(logs[0]);
int returnSize;
int *result = exclusiveTime(2, logs, logsSize, &returnSize);
printf("[");
for (int i = 0; i < returnSize; i++) {
printf("%d%s", result[i], i == returnSize - 1 ? "" : ", ");
}
printf("]\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class ExclusiveTime {
public static int[] ExclusiveTime(int n, IList<string> logs) {
int[] result = new int[n];
Stack<(int id, int time)> stack = new Stack<(int id, int time)>();
int prevTime = 0;
foreach (var log in logs) {
var parts = log.Split(':');
int id = int.Parse(parts[0]);
string type = parts[1];
int time = int.Parse(parts[2]);
if (type == "start") {
if (stack.Count > 0) {
result[stack.Peek().id] += time - prevTime;
}
stack.Push((id, time));
prevTime = time;
} else {
result[stack.Peek().id] += time - prevTime + 1;
stack.Pop();
prevTime = time + 1;
}
}
return result;
}
public static void Main() {
int n = 2;
var logs = new List<string> { "0:start:0", "1:start:2", "1:end:5", "0:end:6" };
int[] result = ExclusiveTime(n, logs);
Console.WriteLine("[" + string.Join(", ", result) + "]");
}
}The Python solution employs a stack to keep track of active functions, where each element is a tuple consisting of a function ID and its start time. It utilizes the log statements to maintain the exclusive times while managing nested functions by continuously updating exclusive times and stack contents.
Time Complexity: O(L), where L is the number of logs.
Space Complexity: O(N), required for the stack representing current active functions.
Approach 2: Using a List to Manage Active Calls
This approach utilizes a list to handle active function calls, with a strategy similar to a stack but implemented differently by directly managing a list. It retains the same core logic to calculate exclusive times by tracking active and nested function calls.
def exclusiveTime(n, logs):
result = [0] * n
active_list = []
prev_time = 0
for log in logs:
id_str, typ, time_str = log.split(':')
id, time = int(id_str), int(time_str)
if typ == 'start':
if active_list:
result[active_list[-1][0]] += time - prev_time
active_list.append((id, time))
prev_time = time
else:
result[active_list[-1][0]] += time - prev_time + 1
active_list.pop()
prev_time = time + 1
return result
# Example usage
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
n = 2
print(exclusiveTime(n, logs)) # Output: [3, 4]import java.util.*;
public class ExclusiveTimeList {
public static int[] exclusiveTime(int n, List<String> logs) {
int[] result = new int[n];
LinkedList<int[]> activeList = new LinkedList<>();
int prevTime = 0;
for (String log : logs) {
String[] parts = log.split(":");
int id = Integer.parseInt(parts[0]);
String type = parts[1];
int time = Integer.parseInt(parts[2]);
if (type.equals("start")) {
if (!activeList.isEmpty()) {
result[activeList.getLast()[0]] += time - prevTime;
}
activeList.add(new int[]{id, time});
prevTime = time;
} else {
result[activeList.getLast()[0]] += time - prevTime + 1;
activeList.removeLast();
prevTime = time + 1;
}
}
return result;
}
public static void main(String[] args) {
List<String> logs = Arrays.asList("0:start:0", "1:start:2", "1:end:5", "0:end:6");
int n = 2;
int[] result = exclusiveTime(n, logs);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> result(n, 0);
vector<pair<int, int>> activeList;
int prevTime = 0;
for (const string& log : logs) {
int id, time;
char event[6];
sscanf(log.c_str(), "%d:%[^:]:%d", &id, event, &time);
if (string(event) == "start") {
if (!activeList.empty()) {
result[activeList.back().first] += time - prevTime;
}
activeList.push_back({id, time});
prevTime = time;
} else { // "end"
result[activeList.back().first] += time - prevTime + 1;
activeList.pop_back();
prevTime = time + 1;
}
}
return result;
}
int main() {
vector<string> logs = { "0:start:0", "1:start:2", "1:end:5", "0:end:6" };
int n = 2;
vector<int> result = exclusiveTime(n, logs);
cout << "[";
for (size_t i = 0; i < result.size(); ++i) {
cout << result[i] << (i == result.size() - 1 ? "" : ", ");
}
cout << "]\n";
return 0;
}function exclusiveTime(n, logs) {
let result = new Array(n).fill(0);
let activeList = [];
let prevTime = 0;
logs.forEach(log => {
let [id, type, timestamp] = log.split(':');
id = parseInt(id);
timestamp = parseInt(timestamp);
if (type === 'start') {
if (activeList.length !== 0) {
result[activeList[activeList.length - 1][0]] += timestamp - prevTime;
}
activeList.push([id, timestamp]);
prevTime = timestamp;
} else { // "end"
result[activeList.pop()[0]] += timestamp - prevTime + 1;
prevTime = timestamp + 1;
}
});
return result;
}
// Example usage
let logs = ["0:start:0","1:start:2","1:end:5","0:end:6"];
let n = 2;
console.log(exclusiveTime(n, logs)); // Output: [3, 4]#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_LOGS 500
#define MAX_FUNC 100
typedef struct {
int id;
int startTime;
} ActiveFunction;
int *exclusiveTime(int n, char logs[][20], int logsSize, int* returnSize) {
int *result = (int *)calloc(n, sizeof(int));
ActiveFunction activeList[MAX_LOGS];
int listSize = 0, prevTime = 0;
for (int i = 0; i < logsSize; i++) {
int id, time;
char event[6];
sscanf(logs[i], "%d:%[^:]:%d", &id, event, &time);
if (strcmp(event, "start") == 0) {
if (listSize > 0) {
result[activeList[listSize - 1].id] += time - prevTime;
}
activeList[listSize++] = (ActiveFunction){id, time};
prevTime = time;
} else { // "end"
result[activeList[listSize - 1].id] += time - prevTime + 1;
listSize--;
prevTime = time + 1;
}
}
*returnSize = n;
return result;
}
int main() {
char logs[][20] = { "0:start:0", "1:start:2", "1:end:5", "0:end:6" };
int logsSize = sizeof(logs) / sizeof(logs[0]);
int returnSize;
int* result = exclusiveTime(2, logs, logsSize, &returnSize);
printf("[");
for (int i = 0; i < returnSize; i++) {
printf("%d%s", result[i], i == returnSize - 1 ? "" : ", ");
}
printf("]\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class ExclusiveTimeList {
public static int[] ExclusiveTime(int n, IList<string> logs) {
int[] result = new int[n];
List<(int id, int time)> activeList = new List<(int id, int time)>();
int prevTime = 0;
foreach (var log in logs) {
var parts = log.Split(':');
int id = int.Parse(parts[0]);
string type = parts[1];
int time = int.Parse(parts[2]);
if (type == "start") {
if (activeList.Count > 0) {
result[activeList[activeList.Count - 1].id] += time - prevTime;
}
activeList.Add((id, time));
prevTime = time;
} else {
result[activeList[activeList.Count - 1].id] += time - prevTime + 1;
activeList.RemoveAt(activeList.Count - 1);
prevTime = time + 1;
}
}
return result;
}
public static void Main() {
int n = 2;
var logs = new List<string> { "0:start:0", "1:start:2", "1:end:5", "0:end:6" };
int[] result = ExclusiveTime(n, logs);
Console.WriteLine("[" + string.Join(", ", result) + "]");
}
}In the Python implementation, a list is used in place of a stack to keep track of active functions. The solution updates exclusive times by iterating over the logs while using list operations to simulate stack behavior for managing function states and calculating execution periods.
Time Complexity: O(L), where L is the number of log entries.
Space Complexity: O(N), due to the list storing active function start times and IDs.
Approach 3: Stack + Simulation
We define a stack stk to store the identifiers of the currently executing functions. We also define an array ans to store the exclusive time of each function, initially setting the exclusive time of each function to 0. We use a variable pre to record the previous timestamp.
We traverse the log array. For each log entry, we first split it by colons to get the function identifier i, the operation type op, and the timestamp t.
If op is start, it means function i starts executing. We need to check if the stack is empty. If it is not empty, we add cur - pre to the exclusive time of the function at the top of the stack, then push i onto the stack and update pre to cur. If op is end, it means function i finishes executing. We add cur - pre + 1 to the exclusive time of the function at the top of the stack, then pop the top element from the stack and update pre to cur + 1.
Finally, we return the array ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the log array.
function exclusiveTime(n: number, logs: string[]): number[] {
const ans: number[] = Array(n).fill(0);
let pre = 0;
const stk: number[] = [];
for (const log of logs) {
const [i, op, cur] = log.split(':');
if (op[0] === 's') {
if (stk.length) {
ans[stk.at(-1)!] += +cur - pre;
}
stk.push(+i);
pre = +cur;
} else {
ans[stk.pop()!] += +cur - pre + 1;
pre = +cur + 1;
}
}
return ans;
}func exclusiveTime(n int, logs []string) []int {
ans := make([]int, n)
stk := []int{}
pre := 0
for _, log := range logs {
parts := strings.Split(log, ":")
i, _ := strconv.Atoi(parts[0])
cur, _ := strconv.Atoi(parts[2])
if parts[1][0] == 's' {
if len(stk) > 0 {
ans[stk[len(stk)-1]] += cur - pre
}
stk = append(stk, i)
pre = cur
} else {
ans[stk[len(stk)-1]] += cur - pre + 1
stk = stk[:len(stk)-1]
pre = cur + 1
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-based Approach | Time Complexity: O(L), where L is the number of logs. |
| Using a List to Manage Active Calls | Time Complexity: O(L), where L is the number of log entries. |
| Stack + Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Simulation | O(n) | O(n) | Best general solution. Directly models nested function calls. |
| List to Track Active Calls | O(n) | O(n) | Useful when implementing with array/list operations instead of a stack. |
Frequently asked questions
Is Exclusive Time of Functions easy or hard?
Exclusive Time of Functions is rated Medium on LeetCode. The challenge comes from correctly handling nested calls and adjusting timestamps so parent functions do not count time spent in child functions.
Exclusive Time of Functions Python/Java solution
The solution is typically implemented using a stack and a previous timestamp variable. Python uses a list as a stack, while Java commonly uses Stack or ArrayDeque. Both implementations iterate through logs once and update execution times in O(n) time.
How to solve Exclusive Time of Functions in O(n)?
Parse each log sequentially and maintain a stack of active function IDs. Track a variable for the previous timestamp. When a new function starts, add the elapsed time to the function on top of the stack. When a function ends, finalize its duration and remove it from the stack. Each log contributes constant work, giving O(n) time complexity.
What is the best approach for Exclusive Time of Functions?
The stack-based simulation is the best approach. It mirrors the behavior of a real program call stack where functions start and end in a nested manner. By tracking the currently running function and updating execution time using a previous timestamp pointer, the algorithm processes logs in O(n) time and O(n) space.
Is Exclusive Time of Functions asked at Google/Amazon/Meta?
Problems involving stack-based log processing and nested execution are commonly asked in interviews at companies like Amazon, Google, and Meta. The problem tests understanding of stack simulation, interval accounting, and careful handling of timestamps.
What data structure is used in Exclusive Time of Functions?
The main data structure is a stack that tracks active function calls. The stack ensures the most recently started function is processed first when an end log appears. Arrays are also used to store the final exclusive execution times for each function.
What is the time complexity of Exclusive Time of Functions?
The optimal solution runs in O(n) time where n is the number of logs. Each log entry is processed exactly once, and each function ID is pushed and popped from the stack at most one time. Space complexity is O(n) due to the stack storing active function calls.