Exclusive Time of Functions

Med

#0590Time: O(L), where L is the number of logs. Each log entry is processed exactly once during the traversal.Space: O(L), where L is the number of logs. In the worst-case scenario of deeply nested calls, the recursion depth can be up to L/2, leading to a space complexity proportional to L for the call stack.4 companies

Data structures

Array Stack

Companies

IBM LinkedIn athenahealth Snap

Prompt

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 i^th 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 i^th 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 <= 100
2 <= logs.length <= 500
0 <= function_id < n
0 <= timestamp <= 10⁹
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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the function call hierarchy using recursion. We can define a recursive function that processes a single function call from its "start" log to its matching "end" log. When it encounters a nested function call (another "start" log), it calls itself recursively to process the nested call. The time consumed by these nested calls is then subtracted from the total duration of the parent function call to determine its exclusive time.

Algorithm

Create a helper function, say calculate, that processes logs starting from a given index. This function will handle one full function call (from its start to its end, including any nested calls).
The main function will iterate through the logs. When it encounters a start log that hasn't been processed, it calls the calculate helper.
The calculate function works as follows:
1. Parse the start log to get the function id and startTime.
2. Initialize a variable childTime = 0 to accumulate the time spent in nested functions.
3. Advance to the next log. Keep processing subsequent logs.
4. If a start log is found, it's a nested call. Recursively call calculate for this nested call. The total time of this nested call (which the recursive call returns) is added to childTime.
5. If an end log is found, it must be the matching end for the current function call. Parse it to get the endTime.
6. The total duration for this call is endTime - startTime + 1.
7. The exclusive time is totalDuration - childTime. Add this to the result array for the current id.
8. The function returns the total time it consumed (totalDuration) to its caller.

Walkthrough

In this method, we treat the log sequence as a representation of a call stack. A recursive function can naturally parse this structure. The main idea is to calculate the total time a function is active (from its start to its end) and then subtract the time consumed by any functions it called (child functions). The remaining time is its exclusive execution time.

We can implement a helper function that, given the index of a start log, finds its corresponding end log. While doing so, it accounts for any nested calls by recursively invoking itself. The time spent in these nested calls is summed up and subtracted from the parent's total active time.

1class Solution {2    // Using a global index to be shared across recursive calls3    private int logIndex;4 5    public int[] exclusiveTime(int n, List<String> logs) {6        int[] result = new int[n];7        logIndex = 0;8        while (logIndex < logs.size()) {9            calculate(logs, result);10        }11        return result;12    }13 14    // This function calculates the total time for one function call15    // and recursively calculates time for its children.16    // It returns the total time consumed by this function and its children.17    private int calculate(List<String> logs, int[] result) {18        String[] startLog = logs.get(logIndex).split(":");19        int id = Integer.parseInt(startLog[0]);20        int startTime = Integer.parseInt(startLog[2]);21        int childExecutionTime = 0;22 23        logIndex++; // Move to the next log24 25        // While the next log is a start of a nested function26        while (logIndex < logs.size() && logs.get(logIndex).split(":")[1].equals("start")) {27            childExecutionTime += calculate(logs, result);28        }29 30        // At this point, logIndex points to the end log of the current function31        String[] endLog = logs.get(logIndex).split(":");32        int endTime = Integer.parseInt(endLog[2]);33        logIndex++; // Move past the end log for the next call in the parent34 35        int totalTime = endTime - startTime + 1;36        result[id] += totalTime - childExecutionTime;37 38        return totalTime; // Return total time to the parent39    }40}

Complexity

Time

O(L), where L is the number of logs. Each log entry is processed exactly once during the traversal.

Space

O(L), where L is the number of logs. In the worst-case scenario of deeply nested calls, the recursion depth can be up to L/2, leading to a space complexity proportional to L for the call stack.

Trade-offs

Pros

The recursive structure provides a clear and direct mapping to the nested nature of function calls.

Cons

Can lead to a StackOverflowError if the function call nesting is very deep.
Generally has more overhead than an iterative solution due to function call mechanics.
The logic for managing indices and passing state between recursive calls can be more complex to implement correctly.

This is the most efficient and robust approach. We process the logs in a single pass from beginning to end. A stack is used to maintain the chain of active function calls. The function ID at the top of the stack represents the currently executing function. By keeping track of the time of the last event, we can calculate the duration for which a function ran before being paused by another function's start or before it finished executing.

Algorithm

Initialize an integer array res of size n with zeros to store the exclusive times.
Initialize an empty Stack to store function IDs, representing the call stack.
Initialize a variable prevTime = 0 to store the timestamp of the previous event.
Iterate through each log in the logs list:
1. Parse the log string to get the id, type ('start' or 'end'), and timestamp.
2. If the type is "start": a. If the stack is not empty, the function at the top of the stack (stack.peek()) was running. Update its exclusive time by adding the duration timestamp - prevTime. b. Push the current function's id onto the stack. c. Update prevTime to the current timestamp.
3. If the type is "end": a. The function ending is at the top of the stack. It ran from prevTime until the end of the current timestamp. Update its exclusive time by adding timestamp - prevTime + 1. b. Pop the function id from the stack. c. Update prevTime to timestamp + 1, as the next time interval will start after the current one ends.
After iterating through all logs, the res array will contain the exclusive time for each function.

Walkthrough

The core of this method is to simulate the events on the single-threaded CPU chronologically. We use a stack to mimic the system's call stack. When a function starts, it becomes the currently running function and is pushed onto our stack. When a function ends, it must be the one at the top of the stack, and it gets popped.

The key insight is how to calculate the time intervals. The time between any two consecutive events belongs to the function that was running during that interval. The running function is always the one at the top of the stack.

When a new function B starts at t1, while function A is running (i.e., A is at the top of the stack), A's execution is paused. The time A ran for is the difference between t1 and the time of the previous event. Then B is pushed onto the stack.
When function B ends at t2, it has been running since the last event. Its execution time for this segment is calculated, and it's popped from the stack. The prevTime is then updated to t2 + 1 because the time unit t2 is fully consumed by B's execution.

This single-pass approach efficiently computes the times without the overhead of recursion.

1import java.util.List;2import java.util.Stack;3 4class Solution {5    public int[] exclusiveTime(int n, List<String> logs) {6        int[] res = new int[n];7        Stack<Integer> stack = new Stack<>();8        int prevTime = 0;9 10        for (String log : logs) {11            String[] parts = log.split(":");12            int id = Integer.parseInt(parts[0]);13            String type = parts[1];14            int timestamp = Integer.parseInt(parts[2]);15 16            if (type.equals("start")) {17                if (!stack.isEmpty()) {18                    res[stack.peek()] += timestamp - prevTime;19                }20                stack.push(id);21                prevTime = timestamp;22            } else { // type.equals("end")23                res[stack.peek()] += timestamp - prevTime + 1;24                stack.pop();25                prevTime = timestamp + 1;26            }27        }28        return res;29    }30}

Complexity

Time

O(L), where L is the number of logs. We iterate through the list of logs exactly once, and each operation (stack push/pop, array access) takes constant time.

Space

O(L), where L is the number of logs. The space is dominated by the stack, which in the worst case can hold up to L/2 function IDs (e.g., a chain of L/2 nested calls).

Trade-offs

Pros

Most efficient approach with a single pass over the data.
Iterative nature avoids potential stack overflow errors, making it more robust for deep call chains.
The logic is a direct simulation of the chronological events, which can be easier to reason about than recursion.

Cons

Requires careful handling of time intervals, particularly the +1 adjustment for end times and the update of prevTime to ensure correctness.

Solutions

Solution

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

1class Solution:2    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]: ans = [0] * n stk = [] curr = - 1 for log in logs: t = log . split(':') fid = int(t[0]) ts = int(t[2]) if t[1] == 'start': if stk: ans[stk[- 1]] += ts - curr stk . append(fid) curr = ts else: fid = stk . pop() ans[fid] += ts - curr + 1 curr = ts + 1 return ans

1class Solution {2public:3  vector<int> exclusiveTime(int n, vector<string> &logs) {4    vector<int> ans(n);5    stack<int> stk;6    int curr = -1;7    for (auto &log : logs) {8      char type[10];9      int fid, ts;10      sscanf(log.c_str(), "%d:%[^:]:%d", &fid, type, &ts);11      if (type[0] == 's') {12        if (!stk.empty())13          ans[stk.top()] += ts - curr;14        curr = ts;15        stk.push(fid);16      } else {17        fid = stk.top();18        stk.pop();19        ans[fid] += ts - curr + 1;20        curr = ts + 1;21      }22    }23    return ans;24  }25};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem