# Exclusive Time of Functions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/exclusive-time-of-functions)
Canonical: https://scaleengineer.com/dsa/problems/exclusive-time-of-functions
**Data structures:** Array, Stack
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [LinkedIn](https://scaleengineer.com/companies/linkedin), [athenahealth](https://scaleengineer.com/companies/athenahealth), [Snap](https://scaleengineer.com/companies/snap)
---
## 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](https://en.wikipedia.org/wiki/Call%5Fstack)**: 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:**

![](https://assets.glich.co/dsa/exclusive-time-of-functions/image0.png) 

**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 <= 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.

# Approaches
## Recursive Approach
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    // Using a global index to be shared across recursive calls
    private int logIndex;

    public int[] exclusiveTime(int n, List<String> logs) {
        int[] result = new int[n];
        logIndex = 0;
        while (logIndex < logs.size()) {
            calculate(logs, result);
        }
        return result;
    }

    // This function calculates the total time for one function call
    // and recursively calculates time for its children.
    // It returns the total time consumed by this function and its children.
    private int calculate(List<String> logs, int[] result) {
        String[] startLog = logs.get(logIndex).split(":");
        int id = Integer.parseInt(startLog[0]);
        int startTime = Integer.parseInt(startLog[2]);
        int childExecutionTime = 0;

        logIndex++; // Move to the next log

        // While the next log is a start of a nested function
        while (logIndex < logs.size() && logs.get(logIndex).split(":")[1].equals("start")) {
            childExecutionTime += calculate(logs, result);
        }

        // At this point, logIndex points to the end log of the current function
        String[] endLog = logs.get(logIndex).split(":");
        int endTime = Integer.parseInt(endLog[2]);
        logIndex++; // Move past the end log for the next call in the parent

        int totalTime = endTime - startTime + 1;
        result[id] += totalTime - childExecutionTime;

        return totalTime; // Return total time to the parent
    }
}
```
### 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.

## Iterative Single-Pass Approach with a Stack
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.
**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).
**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.
### Explanation
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.

```java
import java.util.List;
import java.util.Stack;

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] res = new int[n];
        Stack<Integer> 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 timestamp = Integer.parseInt(parts[2]);

            if (type.equals("start")) {
                if (!stack.isEmpty()) {
                    res[stack.peek()] += timestamp - prevTime;
                }
                stack.push(id);
                prevTime = timestamp;
            } else { // type.equals("end")
                res[stack.peek()] += timestamp - prevTime + 1;
                stack.pop();
                prevTime = timestamp + 1;
            }
        }
        return res;
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  int[] exclusiveTime(int n, List<String> logs) {
    int[] ans = new int[n];
    Deque<Integer> stk = new ArrayDeque<>();
    int curr = -1;
    for (String log : logs) {
      String[] t = log.split(":");
      int fid = Integer.parseInt(t[0]);
      int ts = Integer.parseInt(t[2]);
      if ("start".equals(t[1])) {
        if (!stk.isEmpty()) {
          ans[stk.peek()] += ts - curr;
        }
        stk.push(fid);
        curr = ts;
      } else {
        fid = stk.pop();
        ans[fid] += ts - curr + 1;
        curr = ts + 1;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    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

```

### CPP

```cpp
class Solution {
public:
  vector<int> exclusiveTime(int n, vector<string> &logs) {
    vector<int> ans(n);
    stack<int> stk;
    int curr = -1;
    for (auto &log : logs) {
      char type[10];
      int fid, ts;
      sscanf(log.c_str(), "%d:%[^:]:%d", &fid, type, &ts);
      if (type[0] == 's') {
        if (!stk.empty())
          ans[stk.top()] += ts - curr;
        curr = ts;
        stk.push(fid);
      } else {
        fid = stk.top();
        stk.pop();
        ans[fid] += ts - curr + 1;
        curr = ts + 1;
      }
    }
    return ans;
  }
};

```