Watch 10 video solutions for Exclusive Time of Functions, a medium level problem involving Array, Stack. This walkthrough by Cracking FAANG has 14,705 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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"end" log for each "start" log.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 | 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. |