# LeetCode 636: Exclusive Time of Functions

## Problem Restatement

We are given `n` functions with IDs from `0` to `n - 1`.

We also receive a list of logs. Each log has this format:

```python
"{function_id}:{start_or_end}:{timestamp}"
```

For example:

```python
"0:start:3"
```

means function `0` starts at the beginning of timestamp `3`.

```python
"1:end:5"
```

means function `1` ends at the end of timestamp `5`.

The CPU is single-threaded, so only one function runs at a time. A function may call another function, including itself recursively.

We need to return the exclusive time of every function.

Exclusive time means the time spent running that function itself, excluding time spent inside functions it called.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` and list of log strings `logs` |
| Output | Array `answer`, where `answer[i]` is the exclusive time of function `i` |
| Function IDs | From `0` to `n - 1` |
| Log order | Logs are sorted by timestamp |
| End timestamp | Inclusive |

Example function shape:

```python
def exclusiveTime(n: int, logs: list[str]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
n = 2
logs = [
    "0:start:0",
    "1:start:2",
    "1:end:5",
    "0:end:6",
]
```

Timeline:

| Time | Running Function |
|---:|---:|
| 0 | 0 |
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
| 6 | 0 |

Function `0` runs at timestamps `0`, `1`, and `6`.

So its exclusive time is:

```python
3
```

Function `1` runs at timestamps `2`, `3`, `4`, and `5`.

So its exclusive time is:

```python
4
```

The answer is:

```python
[3, 4]
```

## First Thought: Simulate Every Timestamp

A direct approach is to simulate time unit by time unit.

At each timestamp, we track which function is running and add `1` to that function's time.

This is conceptually simple, but timestamps can be large. We do not want to iterate over every single timestamp.

Instead, we should process intervals between logs.

## Key Insight

At any time, the currently running function is the one at the top of the call stack.

When a function starts, it pauses the current top function.

When a function ends, it is popped from the stack, and the previous function resumes.

We also keep a variable `prev_time`, which means:

```text
the first timestamp not yet assigned to any function
```

When we see a new log at timestamp `t`, the function currently on top of the stack has been running from `prev_time` up to just before `t` if this is a start log.

For an end log, the function runs from `prev_time` through `t`, because end timestamps are inclusive.

That inclusive end is the main detail.

## Algorithm

Create:

```python
answer = [0] * n
stack = []
prev_time = 0
```

For each log:

1. Parse `function_id`, `event`, and `timestamp`.
2. If the event is `"start"`:
   1. If the stack is not empty, add `timestamp - prev_time` to the function on top.
   2. Push the new function ID.
   3. Set `prev_time = timestamp`.
3. If the event is `"end"`:
   1. Pop the function from the stack.
   2. Add `timestamp - prev_time + 1` to that function.
   3. Set `prev_time = timestamp + 1`.

Return `answer`.

## Implementation

```python
class Solution:
    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:
        answer = [0] * n
        stack = []
        prev_time = 0

        for log in logs:
            function_id_str, event, timestamp_str = log.split(":")
            function_id = int(function_id_str)
            timestamp = int(timestamp_str)

            if event == "start":
                if stack:
                    answer[stack[-1]] += timestamp - prev_time

                stack.append(function_id)
                prev_time = timestamp

            else:
                finished_function = stack.pop()
                answer[finished_function] += timestamp - prev_time + 1
                prev_time = timestamp + 1

        return answer
```

## Code Explanation

The result array stores exclusive time for each function:

```python
answer = [0] * n
```

The stack stores active function calls:

```python
stack = []
```

The top of the stack is the function currently running.

The variable:

```python
prev_time = 0
```

marks the next timestamp that still needs to be counted.

For a start log:

```python
if event == "start":
```

the currently running function, if any, has run from `prev_time` to `timestamp - 1`.

So we add:

```python
answer[stack[-1]] += timestamp - prev_time
```

Then we push the newly started function:

```python
stack.append(function_id)
```

and reset `prev_time`:

```python
prev_time = timestamp
```

For an end log:

```python
finished_function = stack.pop()
```

the ending function has run from `prev_time` through `timestamp`.

That is:

```python
timestamp - prev_time + 1
```

The `+1` is required because the end timestamp is included.

After the function ends at the end of `timestamp`, the next available time is:

```python
timestamp + 1
```

So we set:

```python
prev_time = timestamp + 1
```

## Correctness

The stack always represents the active function calls that have started but have not ended. Since the CPU is single-threaded, the function at the top of the stack is the only function running.

Whenever a `"start"` log appears at timestamp `t`, the previous top function stops running at the beginning of `t`. Therefore, it has executed exactly `t - prev_time` units since the last processed timestamp, and the algorithm adds that amount to its exclusive time.

Whenever an `"end"` log appears at timestamp `t`, the top function continues running through the end of timestamp `t`. Therefore, it has executed exactly `t - prev_time + 1` units since the last processed timestamp, and the algorithm adds that amount to its exclusive time before popping it from the stack.

After each log, `prev_time` is updated to the next timestamp that has not yet been counted. This ensures every time unit is charged exactly once to the function running during that time.

Thus the algorithm computes exactly the exclusive execution time for every function.

## Complexity

Let `m` be the number of logs.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m)` | Each log is parsed and processed once |
| Space | `O(n + m)` | The answer array uses `O(n)`, and the stack may hold nested calls |

The stack depth is at most the number of active nested calls.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.exclusiveTime(2, [
        "0:start:0",
        "1:start:2",
        "1:end:5",
        "0:end:6",
    ]) == [3, 4]

    assert s.exclusiveTime(1, [
        "0:start:0",
        "0:end:0",
    ]) == [1]

    assert s.exclusiveTime(2, [
        "0:start:0",
        "0:start:2",
        "0:end:5",
        "1:start:6",
        "1:end:6",
        "0:end:7",
    ]) == [7, 1]

    assert s.exclusiveTime(2, [
        "0:start:0",
        "0:end:1",
        "1:start:2",
        "1:end:3",
    ]) == [2, 2]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Nested function call | Standard stack behavior |
| Start and end at same timestamp | Inclusive end gives time `1` |
| Recursive function call | Same function ID can appear multiple times on the stack |
| Sequential calls | No nesting, direct interval counting |