Table of Contents

# Exclusive Time of Functions – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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`

log message formatted as a string ^{th}`"{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`

`1 <= logs.length <= 500`

`0 <= function_id < n`

`0 <= timestamp <= 10`

^{9}- 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.

# C++ Exclusive Time of Functions LeetCode Solution

```
```The idea is simple everytime we see a start, we just push it to the stack. Now when we reach an end, we are guaranteed that the top of the stack is a start with the same id as the current item because all completed start/ends in between this start and end has been removed already. We just add current item timestamp – stack top timestamp + 1 to times[i].

So for example

[…, {0:start:3}] and item = {0:end:6} we add 6 – 3 + 1

However, what if there are function calls in between the start and end of the function of id 0? We can account for this by subtracting the length of the function calls in between the function id 0 whenever we complete an inner function marked by an end.

[…, {0:start:3}, {2:start:4}] and item = {2:end:5} so we increment times[2] by curr_length = 5 – 4 + 1 = 2 and then we subtract times[0] by curr_length as it takes up that amount of time out of the total time

So whenever we see an end, we have to make sure to subtract our curr_length to whatever function is enclosing it if it exists.

```
#include <iostream>
#include <vector>
#include <stack>
#include <sstream>
#include <cassert>
using namespace std;
struct Log {
int id;
string status;
int timestamp;
};
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> times(n, 0);
stack<Log> st;
for(string log: logs) {
stringstream ss(log);
string temp, temp2, temp3;
getline(ss, temp, ':');
getline(ss, temp2, ':');
getline(ss, temp3, ':');
Log item = {stoi(temp), temp2, stoi(temp3)};
if(item.status == "start") {
st.push(item);
} else {
assert(st.top().id == item.id);
int time_added = item.timestamp - st.top().timestamp + 1;
times[item.id] += time_added;
st.pop();
if(!st.empty()) {
assert(st.top().status == "start");
times[st.top().id] -= time_added;
}
}
}
return times;
}
};
```

# Java Exclusive Time of Functions LeetCode Solution

```
```
- Extract the log parsing logic as a inner class.
- Calculate the function’s running time when encounter an “end” log entry. If current ended func has a main func still running (in the stack), substract the running time advance. So we
**don’t need** to use a “prev” variable.
- Another idea is using a field in the inner class to track the real running time for a function. I believe this way would be the most straightforward for myself.
- Both methods follows the O(n) time complexiy, and O(n/2) extra space consumption.

Method 1

```
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
Deque<Log> stack = new ArrayDeque<>();
int[] result = new int[n];
for (String content : logs) {
Log log = new Log(content);
if (log.isStart) {
stack.push(log);
} else {
Log top = stack.pop();
result[top.id] += (log.time - top.time + 1);
if (!stack.isEmpty()) {
result[stack.peek().id] -= (log.time - top.time + 1);
}
}
}
return result;
}
public static class Log {
public int id;
public boolean isStart;
public int time;
public Log(String content) {
String[] strs = content.split(":");
id = Integer.valueOf(strs[0]);
isStart = strs[1].equals("start");
time = Integer.valueOf(strs[2]);
}
}
}
```

Method 2

```
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
Deque<Log> stack = new ArrayDeque<>();
int[] result = new int[n];
int duration = 0;
for (String content : logs) {
Log log = new Log(content);
if (log.isStart) {
stack.push(log);
} else {
Log top = stack.pop();
result[top.id] += (log.time - top.time + 1 - top.subDuration);
if (!stack.isEmpty()) {
stack.peek().subDuration += (log.time - top.time + 1);
}
}
}
return result;
}
public static class Log {
public int id;
public boolean isStart;
public int time;
public int subDuration;
public Log(String content) {
String[] strs = content.split(":");
id = Integer.valueOf(strs[0]);
isStart = strs[1].equals("start");
time = Integer.valueOf(strs[2]);
subDuration = 0;
}
}
}
```

# Python 3 Exclusive Time of Functions LeetCode Solution

```
```We examine two approaches – both will be stack based.

In a more conventional approach, let’s look between adjacent events, with duration `time - prev_time`

. If we started a function, and we have a function in the background, then it was running during this time. Otherwise, we ended the function that is most recent in our stack.

```
def exclusiveTime(self, N, logs):
ans = [0] * N
stack = []
prev_time = 0
for log in logs:
fn, typ, time = log.split(':')
fn, time = int(fn), int(time)
if typ == 'start':
if stack:
ans[stack[-1]] += time - prev_time
stack.append(fn)
prev_time = time
else:
ans[stack.pop()] += time - prev_time + 1
prev_time = time + 1
return ans
```

In the second approach, we try to record the “penalty” a function takes. For example, if function 0 is running at time [1, 10], and function 1 runs at time [3, 5], then we know function 0 ran for 10 units of time, less a 3 unit penalty. The idea is this: **Whenever a function completes using T time, any functions that were running in the background take a penalty of T.** Here is a slow version to illustrate the idea:

```
def exclusiveTime(self, N, logs):
ans = [0] * N
#stack = SuperStack()
stack = []
for log in logs:
fn, typ, time = log.split(':')
fn, time = int(fn), int(time)
if typ == 'start':
stack.append(time)
else:
delta = time - stack.pop() + 1
ans[fn] += delta
#stack.add_across(delta)
stack = [t+delta for t in stack] #inefficient
return ans
```

This code already ACs, but it isn’t efficient. However, we can easily upgrade our stack to a “superstack” that supports `self.add_across`

: addition over the whole array in constant time.

```
class SuperStack(object):
def __init__(self):
self.A = []
def append(self, x):
self.A.append([x, 0])
def pop(self):
x, y = self.A.pop()
if self.A:
self.A[-1][1] += y
return x + y
def add_across(self, y):
if self.A:
self.A[-1][1] += y
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1