Exclusive Time of Functions — Solution in Python, Java & C++
Exclusive Time of Functions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Exclusive Time of Functions is a medium coding problem on arrays and stack, asked in Amazon, Meta, Uber and LinkedIn interviews.
- Difficulty: Medium
- Topics: Arrays, Stack
- Asked at: Amazon, Meta, Uber, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A single-threaded CPU runs a program made of n functions with ids 0 to n - 1. Calls may nest (a function may call another, or itself), and the CPU always runs the most recently started call that has not finished yet.
Every call is recorded by two entries in logs, given in chronological order, each written "{id}:start:{t}" or "{id}:end:{t}". A start at t means the call begins at the beginning of time unit t; an end at t means it finishes at the end of time unit t. So "0:start:3" followed by "0:end:4" is a call that ran for 2 units.
The exclusive time of a function is the total number of units the CPU spent running its own calls — time spent inside the calls it makes does not count. Return an array whose i-th value is the exclusive time of function i.
Example 1
Input: n = 2, logs = ["0:start:0","1:start:3","1:end:4","0:end:7"]
Output: [6,2]
Explanation: Function 0 runs units 0–2 and 5–7 (6 units); function 1 runs units 3–4.
Example 2
Input: n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:end:6"]
Output: [7]
Explanation: The recursive call covers units 2–5 and the outer call units 0–1 and 6; both count for function 0.
Example 3
Input: n = 3, logs = ["0:start:0","0:end:1","2:start:2","2:end:2","1:start:4","1:end:4"]
Output: [2,1,1]
Explanation: The CPU is idle during unit 3.
Constraints
1 <= n <= 1002 <= logs.length <= 5000 <= id < n0 <= t <= 10^9No two start entries share a timestamp, and no two end entries share a timestamp.Every start has a matching end, and the log is properly nested.
Hints for Exclusive Time of Functions
Hint 1
The function running at any moment is the one on top of the call stack.
Hint 2
Keep a pointer
prevto the first time unit not yet credited to anyone. Every log entry credits the stretch sinceprevto whoever was on top.Hint 3
On a start at
t, the old top earnst - prevandprev = t. On an end att, the finishing call earnst - prev + 1andprev = t + 1.
How to solve Exclusive Time of Functions
Replay the log with a stack of active calls. Between two consecutive entries exactly one function — the top of the stack — owns the CPU, so each entry closes a stretch of time and credits it to that function.
Approach
- Create
resof sizen, an empty stack, andprev = 0, the first unit not yet credited. - Parse each entry into
id, kind andt. - Start: if the stack is not empty, add
t - prevto the top function; pushid; setprev = t. - End: pop the top (it is
id), addt - prev + 1to it, and setprev = t + 1because unittis fully used. - Return
res.
Why it works
The stack mirrors the real call stack, so its top is always the running function. Every time unit between the first start and the last end belongs to the segment between two consecutive entries, and each segment is credited exactly once — to the call that was running through it. Idle gaps between top-level calls happen while the stack is empty and are credited to nobody.
Complexity
- Time —
O(L) for L log entries (each is parsed once) - Space —
O(L) for the stack
Pitfalls
- Starts and ends use different boundaries: a start begins at
t, an end finishes aftert— hence the+ 1on ends andprev = t + 1. - Recursion means the same id can be on the stack several times; credit the top entry, not a per-id timer.
- Parse the timestamp as a number — comparing strings would order
10before9.
Reference solution
Python
from typing import List
def exclusiveTime(n: int, logs: List[str]) -> List[int]:
res = [0] * n
stack = []
prev = 0
for entry in logs:
fid, kind, ts = entry.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 resJava
public static int[] exclusiveTime(int n, String[] logs) {
int[] res = new int[n];
int[] stack = new int[logs.length];
int top = 0, prev = 0;
for (String entry : logs) {
String[] parts = entry.split(":");
int id = Integer.parseInt(parts[0]);
int t = Integer.parseInt(parts[2]);
if (parts[1].equals("start")) {
if (top > 0) res[stack[top - 1]] += t - prev;
stack[top++] = id;
prev = t;
} else {
res[stack[--top]] += t - prev + 1;
prev = t + 1;
}
}
return res;
}C++
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> res(n, 0);
vector<int> st;
int prev = 0;
for (const string& entry : logs) {
size_t a = entry.find(':');
size_t b = entry.find(':', a + 1);
int id = stoi(entry.substr(0, a));
string kind = entry.substr(a + 1, b - a - 1);
int t = stoi(entry.substr(b + 1));
if (kind == "start") {
if (!st.empty()) res[st.back()] += t - prev;
st.push_back(id);
prev = t;
} else {
res[st.back()] += t - prev + 1;
st.pop_back();
prev = t + 1;
}
}
return res;
}JavaScript
var exclusiveTime = function(n, logs) {
var res = new Array(n).fill(0);
var stack = [];
var prev = 0;
for (var i = 0; i < logs.length; i++) {
var parts = logs[i].split(":");
var id = parseInt(parts[0], 10);
var t = parseInt(parts[2], 10);
if (parts[1] === "start") {
if (stack.length > 0) res[stack[stack.length - 1]] += t - prev;
stack.push(id);
prev = t;
} else {
res[stack.pop()] += t - prev + 1;
prev = t + 1;
}
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure