Exclusive Time of Functions
Exclusive Time of Functions is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (stack with previous boundary), runs in O(m) time and O(m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (tick-by-tick simulation) up.
Problem
A single-threaded CPU runs a program made of n functions with ids 0 to n - 1. Functions can call each other (and themselves), so calls nest: when a function calls another, it pauses until the callee returns.
You get logs, sorted by time, where each entry is "id:start:t" (function id begins at the start of time unit t) or "id:end:t" (function id finishes at the end of time unit t).
A function’s exclusive time is the number of units during which it was the one actually running, summed over all its calls. Return an array whose i-th value is the exclusive time of function i.
Examples
Example 1
- Input
n = 2, logs = ["0:start:0", "1:start:3", "1:end:4", "0:end:7"]- Output
[6, 2]- Why
- Function 0 runs during units 0-2 and again during 5-7 (6 units). Function 1 runs during units 3 and 4 (2 units).
Example 2
- Input
n = 1, logs = ["0:start:0", "0:start:2", "0:end:3", "0:end:5", "0:start:8", "0:end:8"]- Output
[7]- Why
- The outer call owns units 0, 1, 4 and 5, the recursive call owns 2 and 3, and the later call owns unit 8: 4 + 2 + 1 = 7.
Example 3
- Input
n = 3, logs = ["2:start:1", "0:start:2", "0:end:2", "1:start:3", "1:end:6", "2:end:9"]- Output
[1, 4, 4]- Why
- Function 0 owns unit 2, function 1 owns units 3-6, and function 2 owns units 1 and 7-9.
Constraints
1 <= n <= 1002 <= logs.length <= 5000 <= function_id < n0 <= timestamp <= 10^9- Logs are sorted by time, every start has a matching end, and calls are properly nested. No two start events share a timestamp, and no two end events share one.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (tick-by-tick simulation) | O(m + T) | O(m) |
| Optimal (stack with previous boundary) | O(m) | O(m) |
1Brute force (tick-by-tick simulation)
O(m + T)m logs, plus one step for every time unit up to the last timestamp T, which can be 10^9.O(m)The call stack can hold up to m / 2 ids.Turn every log into a boundary in time: a start at t happens at the beginning of unit t, an end at t happens after unit t, so at t + 1. Keep a stack of running functions and, between two boundaries, step through every single unit and credit it to the function on top of the stack.
- res = zeros(n), empty stack, prev = 0.
- For each log, compute b = t for a start or t + 1 for an end.
- For every unit u from prev to b - 1: if the stack is not empty, res[top]++.
- Push the id on a start, pop on an end. Set prev = b.
- Return res.
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
int prev = 0;
for (String log : logs) {
String[] p = log.split(":");
int id = Integer.parseInt(p[0]);
int t = Integer.parseInt(p[2]);
boolean start = p[1].equals("start");
int b = start ? t : t + 1;
for (int u = prev; u < b; u++) {
if (!stack.isEmpty()) res[stack.peek()]++;
}
if (start) stack.push(id);
else stack.pop();
prev = b;
}
return res;
}
}class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res = [0] * n
stack = []
prev = 0
for log in logs:
fid, kind, ts = log.split(":")
t = int(ts)
start = kind == "start"
b = t if start else t + 1
for _ in range(prev, b):
if stack:
res[stack[-1]] += 1
if start:
stack.append(int(fid))
else:
stack.pop()
prev = b
return resclass Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> res(n, 0);
vector<int> stack;
long long prev = 0;
for (const string& log : logs) {
size_t a = log.find(':');
size_t c = log.rfind(':');
int id = stoi(log.substr(0, a));
long long t = stoll(log.substr(c + 1));
bool start = log.substr(a + 1, c - a - 1) == "start";
long long b = start ? t : t + 1;
for (long long u = prev; u < b; u++) {
if (!stack.empty()) res[stack.back()]++;
}
if (start) stack.push_back(id);
else stack.pop_back();
prev = b;
}
return res;
}
};function exclusiveTime(n, logs) {
const res = new Array(n).fill(0);
const stack = [];
let prev = 0;
for (const log of logs) {
const [fid, kind, ts] = log.split(":");
const t = Number(ts);
const start = kind === "start";
const b = start ? t : t + 1;
for (let u = prev; u < b; u++) {
if (stack.length > 0) res[stack[stack.length - 1]]++;
}
if (start) stack.push(Number(fid));
else stack.pop();
prev = b;
}
return res;
}2Optimal (stack with previous boundary)
O(m)Each of the m logs is parsed and handled in constant time.O(m)The call stack holds up to m / 2 ids.Same stack and the same boundaries, but credit a whole gap at once: the function on top of the stack gets b - prev units in one addition. A start pauses the current top (it gets t - prev); an end closes the top (it gets t - prev + 1) and the next gap begins at t + 1.
- res = zeros(n), empty stack, prev = 0.
- On
id:start:t: if the stack is not empty, res[top] += t - prev. Push id, prev = t. - On
id:end:t: res[pop()] += t - prev + 1, prev = t + 1. - Return res.
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
int prev = 0;
for (String log : logs) {
String[] p = log.split(":");
int id = Integer.parseInt(p[0]);
int t = Integer.parseInt(p[2]);
if (p[1].equals("start")) {
if (!stack.isEmpty()) res[stack.peek()] += t - prev;
stack.push(id);
prev = t;
} else {
res[stack.pop()] += t - prev + 1;
prev = t + 1;
}
}
return res;
}
}class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res = [0] * n
stack = []
prev = 0
for log in logs:
fid, kind, ts = log.split(":")
t = int(ts)
if kind == "start":
if stack:
res[stack[-1]] += t - prev
stack.append(int(fid))
prev = t
else:
res[stack.pop()] += t - prev + 1
prev = t + 1
return resclass Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> res(n, 0);
vector<int> stack;
int prev = 0;
for (const string& log : logs) {
size_t a = log.find(':');
size_t c = log.rfind(':');
int id = stoi(log.substr(0, a));
int t = stoi(log.substr(c + 1));
if (log.substr(a + 1, c - a - 1) == "start") {
if (!stack.empty()) res[stack.back()] += t - prev;
stack.push_back(id);
prev = t;
} else {
res[stack.back()] += t - prev + 1;
stack.pop_back();
prev = t + 1;
}
}
return res;
}
};function exclusiveTime(n, logs) {
const res = new Array(n).fill(0);
const stack = [];
let prev = 0;
for (const log of logs) {
const [fid, kind, ts] = log.split(":");
const t = Number(ts);
if (kind === "start") {
if (stack.length > 0) res[stack[stack.length - 1]] += t - prev;
stack.push(Number(fid));
prev = t;
} else {
res[stack.pop()] += t - prev + 1;
prev = t + 1;
}
}
return res;
}Edge cases to test
- A call that starts and ends at the same timestamp still takes 1 unit
- Recursive calls: the same id appears several times on the stack, and all of it counts toward that id
- Idle gaps between top-level calls belong to no function
- A child that starts right after its parent starts, or ends right before its parent ends
- Huge timestamps, so you cannot step through time one unit at a time
Hints
Hint 1
A single CPU runs one function at a time, and the calls nest like brackets. Which structure models nested calls?
Hint 2
Keep a stack of running ids. Between two consecutive events, the time belongs to whoever is on top of the stack.
Hint 3
Treat a start at t as the boundary before unit t, and an end at t as the boundary after unit t (that is, t + 1). Then each gap is just the difference between two boundaries.
FAQ
What is the best time complexity for Exclusive Time of Functions?
Optimal (stack with previous boundary) runs in O(m) time and O(m) extra space. Each of the m logs is parsed and handled in constant time.
Which pattern does Exclusive Time of Functions use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Exclusive Time of Functions?
Yes. Brute force (tick-by-tick simulation) takes O(m + T) time and O(m) space. Turn every log into a boundary in time: a start at t happens at the beginning of unit t, an end at t happens after unit t, so at t + 1.
Which edge cases should I test for Exclusive Time of Functions?
A call that starts and ends at the same timestamp still takes 1 unit; Recursive calls: the same id appears several times on the stack, and all of it counts toward that id; Idle gaps between top-level calls belong to no function; A child that starts right after its parent starts, or ends right before its parent ends; Huge timestamps, so you cannot step through time one unit at a time.