# Java Stack Solution O(n) Time O(n) Space

• ``````public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
int prevTime = 0;
for (String log : logs) {
String[] parts = log.split(":");
if (!stack.isEmpty()) res[stack.peek()] +=  Integer.parseInt(parts[2]) - prevTime;
prevTime = Integer.parseInt(parts[2]);
if (parts[1].equals("start")) stack.push(Integer.parseInt(parts[0]));
else {
res[stack.pop()]++;
prevTime++;
}
}
return res;
}
``````

``````public int[] exclusiveTime(int n, List<String> logs) {
// separate time to several intervals, add interval to their function
int[] result = new int[n];
Stack<Integer> st = new Stack<>();
int pre = 0;
// pre means the start of the interval
for(String log: logs) {
String[] arr = log.split(":");
if(arr[1].equals("start")) {
if(!st.isEmpty())  result[st.peek()] += Integer.parseInt(arr[2]) - pre;
// arr[2] is the start of next interval, doesn't belong to current interval.
st.push(Integer.parseInt(arr[0]));
pre = Integer.parseInt(arr[2]);
} else {
result[st.pop()] += Integer.parseInt(arr[2]) - pre + 1;
// arr[2] is end of current interval, belong to current interval. That's why we have +1 here
pre = Integer.parseInt(arr[2]) + 1;
// pre means the start of next interval, so we need to +1
}
}
return result;
}``````

• Another Approach.

``````public int[] exclusiveTime(int n, List<String> logs) {
int [] ans = new int [n];
Stack <int []> stack = new Stack <>();
int prev = 0;
for (String log : logs) {
int id = Integer.valueOf (log.split (":") [0]), time = Integer.valueOf (log.split (":") [2]);
String action = log.split (":") [1];
if (action.equals("start")) {
if (!stack.isEmpty()) stack.peek () [1] += (time - prev - 1);
stack.push (new int [] { id, 1 });
} else ans [stack.peek () [0]] += stack.pop () [1] + (time - prev);
prev = time;
}
return ans;
}
``````

• @GardenAAA good explanation, thanks

• nice，the logic is clear

• Good idea to make it concise. Implement your idea in C++

``````class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> result(n, 0);
stack<int> sk;
int prev_time = 0;
for(const string& log:logs) {
bool start = true;
int id = 0, time = 0;
decompose(log, start, id, time);
if(!sk.empty()) result[sk.top()] += time-prev_time;
prev_time = time;
if(start) {
sk.push(id);
}
else {
result[sk.top()]++;
prev_time++;
sk.pop();
}
}
return result;
}
private:
void decompose(const string& log, bool& start, int& id, int& time) {
int i = 0;
while(log[i]!=':') i++;
id = stoi(log.substr(0,i));
start = true;
if(log[++i]=='e') start=false;
if(start) time = stoi(log.substr(i+6, log.length()-i-6));
else time = stoi(log.substr(i+4, log.length()-i-4));
}
};
``````

• @GardenAAA easier to understand

• C++ different approach. I hope it's easy to understand after adding some comments.

``````class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> res(n);
stack<pair<int, int> > stk;

for (int i=0;i<logs.size();i++){
string temp = logs[i];
istringstream ss(temp);
int id, time;
string action;
getline(ss, temp, ':');
id = stoi(temp);
getline(ss, temp, ':');
action = temp;
getline(ss, temp, ':');
time = stoi(temp);

if (action=="start"){
if (!stk.empty()){ //there is already a previous function so lets add the time of execution of previous function until this point
res[stk.top().first] += time-stk.top().second;
}
stk.push({id, time});
}else{
auto curr = stk.top();
stk.pop();
res[curr.first] += time-curr.second+1;
if (!stk.empty()) stk.top().second = time+1;
// we've already counted the time of execution of caller function before this function started.
//So now we only have to account for the time between the current function's end time and caller function's end time.
//This is done by setting the start time for the caller function to be the end time of current function.
}
}
return res;
}
};
``````

• @GardenAAA Thanks for the solution, I like the idea.

• What I do is that for every `start`, i push to the stack. But before pushing, I calculate the time it spent for the peek element.
For every `end`, i pop and compute time. And for the peek element, i update the start time as end time of it.

``````public int[] exclusiveTime(int n, List<String> logs) {
Stack<String[]> s = new Stack<>();
int[] result = new int[n];
for(int i = 0;i < logs.size(); i++) {
String[] log = logs.get(i).split(":");
if(log[1].equals("start")) {
if(!s.isEmpty()) {
String[] top = s.peek();
result[Integer.parseInt(top[0])] += Integer.parseInt(log[2]) - Integer.parseInt(top[2]) - 1;
}
s.push(new String[] {log[0], log[1], log[2]});
}else {
String[] top = s.pop();
result[Integer.parseInt(log[0])] += Integer.parseInt(log[2]) + 1 - Integer.parseInt(top[2]);
if(!s.isEmpty()) {
top = s.peek();
top[2] = log[2];
}
}
}
return result;
}
``````

And you can also notice that log[1] "start" and "end" is not needed to be added to stack. But it could be needed if CPU is not single thread.

• I have similar algorithm, but yours must be faster.

``````class Log {
int id;
String status;
int ts;
Log (int id, String status, int ts) {
this.id = id;
this.status = status;
this.ts = ts;
}
}
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
if (logs == null || logs.size() == 0) return res;
int size = logs.size();
Stack<Log> stack = new Stack<>();//only start status will be stored in stack
int idx = 0;
while (idx < size) {
String[] log = logs.get(idx++).split(":");
Log cur = new Log(Integer.parseInt(log[0]), log[1], Integer.parseInt(log[2]));
if (stack.isEmpty()) stack.push(cur);
else {
Log prev = stack.peek();
if (prev.status.equals(cur.status)) {
res[prev.id] += cur.ts - prev.ts;
stack.push(cur);
} else {
res[prev.id] += cur.ts - prev.ts + 1;
stack.pop();
if (!stack.isEmpty()) {
Log fix = stack.pop();
fix.ts = cur.ts + 1;
stack.push(fix);
}
}
}
}
return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.