Python solution with detailed explanation


  • 0
    G

    Exclusive Time of Functions https://leetcode.com/problems/exclusive-time-of-functions/#/description

    Stack Simulation

    • Use a stack to store state. An item in the stack consists of item_id, event_type, and the time elapsed for that item so far.
    • Maintain a clk to track time in the system.
    • If the stack is empty, simply add the item to the stack. The time elapsed for a newly added entry will be zero.
    • If the stack is not empty and the new item is different from the top of the stack ("0:start:0") OR the new item is same as the top of stack but with the same event type (i.e. recursion example: "0:start:0"->"0:start:2"), then increment the time elapsed for the top item in the stack and add the new item.
    • If the new item is same as top of the stack but the event type is end, then pop the element and store the time elapsed in a dictionary with key as item_id.
    • Example: ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
    • Time complexity is O(N) where is number of logs. Space complexity is also O(N).
    from collections import defaultdict
    class Solution:
        def exclusiveTime(self, n, logs):
            """
            :type n: int
            :type logs: List[str]
            :rtype: List[int]
            """
            st, clk, result = [], 0, defaultdict(int)
            ID, EVENT_TYPE, ELAPSED = 0, 1, 2
            for log in logs:
                items = log.split(":")
                item_id, item_type, item_ts = items[0], items[1], int(items[2])
                if st and st[-1][ID] == item_id and st[-1][EVENT_TYPE] != item_type:
                    elapsed = item_ts+1-clk+st[-1][ELAPSED]
                    clk = item_ts+1
                    result[item_id] += elapsed
                    st.pop()
                else:
                    if st:
                        st[-1][ELAPSED] = st[-1][ELAPSED] + item_ts-clk
                    st.append([item_id, item_type, 0])
                    clk = item_ts
            return [result[str(i)] for i in range(n)]
    

Log in to reply
 

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