Problem statement

https://leetcode.com/problems/exclusive-time-of-functions/

Solution

Not very difficult problem once we understand what to do. First thing which was not obvious for me is that our logs are already sorted by increasing time. Let us iterate over our logs, parse them and consider 2 cases:

  1. op == "start": it means, that we just started new process. In this case we need to check what process we have before started one: we keep this id in the end of our stack. We add passed time to corresponding cell of \texttt{out} result. Also we add new process id to our stack.
  2. op == "end": it means that we need to remove one element from stack and also add passed time to corresponding cell of out. Note, that we also add +1, because of strange statement of this problem: process starts at 0 and ends at 1 spends 2 moments of time.
  3. Finally, we update our last_time: it is either time for start points and time + 1 for end points.

Complexity

Time and space complexity is O(m), where m is number of elements in logs.

Code

class Solution:
    def exclusiveTime(self, N, logs):
        stack, out, last_time = [], [0]*N, 0 
    
        for log in logs:
            ind, op, time = log.split(':')
            ind, time = int(ind), int(time)

            if op == "start":
                if stack:
                    out[stack[-1]] += time - last_time 
                stack += [ind]
            else:
                out[stack.pop()] += time - last_time + 1
                
            last_time = time + (op == "end")

        return out