DSA Stacks

Exclusive Time of Functions

Stack of currently-running functions; on each log line, charge elapsed time to the stack top.

Medium
Time O(L) Space O(n)
LeetCode
4 min read
stack simulation parsing

Problem#

Given function-call logs of the form "id:start:t" or "id:end:t" on a single thread, return each function’s exclusive run time.

Examples#

  • n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"][3,4]
  • n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"][8]

Constraints#

  • 1 <= n <= 100, 1 <= logs.length <= 500.

Approach#

Stack stores currently-running function ids. Maintain prev = the timestamp of the last event. On any log line, charge (t - prev) to the function currently on top. On start, push the new function. On end, pop and advance prev = t + 1 (the function ran through the end of that tick); otherwise prev = t.

Solution#

Exclusive Time of Functions
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> ans(n, 0);
stack<int> st;
int prev = 0;
for (auto& line : logs) {
int p1 = line.find(':'), p2 = line.find(':', p1 + 1);
int id = stoi(line.substr(0, p1));
string ev = line.substr(p1 + 1, p2 - p1 - 1);
int t = stoi(line.substr(p2 + 1));
if (ev == "start") {
if (!st.empty()) ans[st.top()] += t - prev;
st.push(id);
prev = t;
} else {
ans[st.top()] += t - prev + 1;
st.pop();
prev = t + 1;
}
}
return ans;
}
};

Editorial#

Time is one-dimensional: between consecutive events, the function on the stack top “owns” the CPU. The +1 on end is because both start and end happen at the beginning of their tick — so an end at time t includes tick t itself.

Complexity#

  • Time: O(L) where L is total log length.
  • Space: O(n).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.