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 ith log message formatted as a string "{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 ith index represents the exclusive time for the function with ID i.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 100
	1 &lt;= logs.length &lt;= 500
	0 &lt;= function_id &lt; n
	0 &lt;= timestamp &lt;= 109
	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.


class Solution:
    #T=O(n), S=O(d)
    #n=len of logs, d=depth of stack
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        #init result array to zeroes of length n (function ids)
        res = [0]*n
        stack = []
        #iterate through logs
        for log in logs:
            #split the log
            #function_id: start|end: timestamp
            log = log.split(":")
            #type cast function id and timestamp to int type
            id = int(log[0])
            timestamp = int(log[2])
            state = log[1]
            #detect start of a function call
            #stack[function_id, start_timestamp]
            if state == "start":
                #stack is non empty
                if stack:
                    #get the time taken by last function so far
                    res[stack[-1][0]] += timestamp - stack[-1][1]
                #append the current function_id and start timestamp to the stack
                stack.append([id, timestamp])
            else:
                #get the time consumed by current function
                #dont forget to add 1 as the last unit of time should be included
                res[id] += timestamp - stack.pop()[1] + 1
                if stack:
                    #update the start time of last function in stack to get the cumulative result
                    stack[-1][1] = timestamp + 1

        return res
class Solution {

    //Time Complexity: O(N) for looping through logs
    //Space Complexity: O(N) for stack

    public int[] exclusiveTime(int n, List<String> logs) {
        if (n == 0) {
            return new int[0];
        }

        int[] result = new int[n];

        Stack<Pair<Integer, Integer>> stack = new Stack<>();

        for (String s : logs) {
            String[] sArr = s.split(":");
            int functionId = Integer.parseInt(sArr[0]);
            String startOrEnd = sArr[1];
            int timestamp = Integer.parseInt(sArr[2]);

            if (startOrEnd.equals("start")) {

                //calculate previous in-progress length
                if (!stack.empty()) {
                    Pair<Integer, Integer> pair = stack.peek();
                    int oldFunctionId = pair.getKey();
                    int oldTimestamp = pair.getValue();
                    result[oldFunctionId] += timestamp - oldTimestamp;
                }

                //add new start
                stack.push(new Pair(functionId, timestamp));
            } else {
                //calculate current length
                Pair<Integer, Integer> pair = stack.pop();
                int oldTimestamp = pair.getValue();

                result[functionId] += timestamp - oldTimestamp + 1;

                //reset previous function's start
                if (!stack.empty()) {
                    pair = stack.pop();
                    Pair<Integer, Integer> replacementPair = new Pair(pair.getKey(), timestamp + 1);
                    stack.push(replacementPair);
                }
            }
        }

        return result;
    }
}
class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> ret(n, 0);
        stack<pair<int, int>> st;
        for (auto& l : logs) {
            auto p1 = l.find(':', 0), p2 = l.find(':', p1+1);
            auto id = stoi(l.substr(0, p1));
            auto time = stoi(l.substr(p2+1));
            if (l[p1+1] == 's') {
                st.push({id, time});
            } else {
                auto diff = time - st.top().second + 1;
                ret[st.top().first] += diff;
                st.pop();
                if (!st.empty())
                    ret[st.top().first] -= diff;
            }
        }
        return ret;
    }
};
var exclusiveTime = function(n, logs) {
	const stack = [];
	let preTimeStamp = 0;

	return logs.reduce((times, log) => {
		const [id, status, timeStamp] = log.split(':');
		const time = +timeStamp - preTimeStamp;
		const { length } = stack;

		if (length) {
			const lastId = stack[length - 1];
			times[lastId] += time;
		}
		preTimeStamp = +timeStamp;

		if (status === 'start') stack.push(id);
		else {
			const lastId = stack.pop();
			times[lastId] += 1;
			preTimeStamp += 1;
		}
		return times;
	}, Array(n).fill(0));
}
Exclusive Time of Functions