Python, O(logs.size) time, O(n) space

  • 0

    Overall, the approach below uses a stack, we push (fid, start_timestamp) to the stack for start of each function call. It also records net runtime of calls at each depth in a hashmap which can have O(n) size in the worst case because the max depth or max stack size is n.

    To understand this problem and solution better, consider a simpler version of the given problem where we would just have to compute the net runtime (end_timestamp - start_timestamp + 1) of each function and not the "Exclusive runtime". That problem would be relatively simpler, because as soon as we pop a function out of the stack (whenever an end is seen) we could compute its net runtime using current (end) timestamp and old (start) timestamp without having to worry about "excluding" inner function call time.

    But in this problem we have to compute the "Exclusive runtime". Exclusive runtime implies the net runtime of a function call minus net runtime of all inner calls (inner functions/calls are those that were called by the outer function). So we just maintain the net runtime (of all function calls) at each depth. And to compute exclusive runtime at a given depth we subtract net runtime of next depth (i.e. net runtime of all inner functions) from the outer function's run time. Here is the code as per the explanation (with inline comments):

    def exclusiveTime(self, n, logs):
        ans = [0]*n
        s = []
        depth = 0
        # Records net runtime at each depth
        druntime = collections.defaultdict(int)
        for line in logs:
            fid, marker, t = line.split(':')
            fid, t = int(fid), int(t)
            if marker == 'start':
                depth += 1
                s.append((fid, t))
                druntime[depth+1] = 0                    # Reset inner depth runtime when new function starts
                fid, start_ts = s.pop()
                runtime = t - start_ts + 1               # Runtime for function just popped
                druntime[depth] += runtime               # Net runtime for all function calls at this depth
                ans[fid] += runtime - druntime[depth+1]  # Exclsv time = Runtime - Runtime of inner depth
                depth -= 1
        return ans

Log in to reply

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