Exclusive Time of functions

78.Exclusive Time of Functions

Stack

Simulation

Problem Statement:

Given the number of functions n and a list of execution logs, return an array where result[i] is the total exclusive time of the i-th function. Exclusive time is the total time a function spends executing, excluding time spent in nested function calls.

Algorithm:

1. Initialize a result array to track the exclusive time for each function.
2. Use a stack to track active functions by their IDs.
3. Iterate through each log in the input:
• If the log is a start event, update the time for the current function on the stack, push the new function, and update the previous timestamp.
• If the log is an end event, update the exclusive time for the function on top of the stack, pop it, and update the previous timestamp to reflect the next interval.
4. Return the result array after processing all logs.

Complexity:

Time: O(n) | Space: O(n)

Java Implementation:

public int[] exclusiveTime(int n, List logs) {
    // The result array will hold the total exclusive execution time for each function.
    // "exclusive execution time" means the total time spent executing that function 
    // itself, not including time spent in nested function calls.
    int[] res = new int[n];
    
    // A stack to keep track of the currently running function IDs. 
    // When a function "starts", we push its ID; when it "ends", we pop.
    Stack stack = new Stack<>();
    
    // Parse the first log entry: 
    // Each log is in the format "function_id:start_or_end:timestamp"
    // e.g. "0:start:0" or "1:end:2"
    String[] log = logs.get(0).split(":");
    stack.push(Integer.parseInt(log[0]));   // Push the first function ID onto the stack.
    int i = 1;                               // Start iterating from the second log entry.
    int prev = Integer.parseInt(log[2]);     // 'prev' records the previous timestamp we've processed.
    
    while (i < logs.size()) {
        log = logs.get(i).split(":");
        
        if (log[1].equals("start")) {
            // If the current log is a start event:
            // 1. The currently running function (on top of the stack) has been interrupted.
            //    So we update its exclusive time by adding the difference between the current start time 
            //    and the previous timestamp. This accounts for the time the top function was running 
            //    before this new start.
            if (!stack.isEmpty()) {
                res[stack.peek()] += Integer.parseInt(log[2]) - prev;
            }
            
            // 2. Push the new function ID onto the stack (it becomes the current function).
            stack.push(Integer.parseInt(log[0]));
            
            // 3. Update 'prev' to the new start time.
            prev = Integer.parseInt(log[2]);
            
        } else {
            // If the current log is an end event:
            // 1. The function at the top of the stack is ending right now.
            //    Update its exclusive time by adding the difference between the end time and prev.
            //    Note: For end events, we add (endTime - prev + 1) 
            //    because if a function starts at time t and ends at time t, 
            //    it still executed for 1 unit of time.
            res[stack.peek()] += Integer.parseInt(log[2]) - prev + 1;
            
            // 2. Update 'prev' to one plus the current end time, because the next interval 
            //    starts right after this function ends.
            prev = Integer.parseInt(log[2]) + 1;
            
            // 3. Pop the ended function off the stack.
            stack.pop();
        }
        
        // Move to the next log entry.
        i++;
    }

    return res;
}

Python Implementation:

def exclusiveTime(n, logs):
    res = [0] * n
    stack = []
    prev = int(logs[0].split(":")[2])
    
    for log in logs:
        func_id, event, timestamp = log.split(":")
        func_id, timestamp = int(func_id), int(timestamp)
        
        if event == "start":
            if stack:
                res[stack[-1]] += timestamp - prev
            stack.append(func_id)
            prev = timestamp
        else:
            res[stack.pop()] += timestamp - prev + 1
            prev = timestamp + 1
    
    return res

C++ Implementation:

#include 
#include 
#include 
using namespace std;

vector exclusiveTime(int n, vector& logs) {
    vector res(n, 0);
    stack stack;
    int prev = stoi(logs[0].substr(logs[0].find_last_of(":") + 1));
    
    for (const string& log : logs) {
        size_t colon1 = log.find(":");
        size_t colon2 = log.find(":", colon1 + 1);
        
        int func_id = stoi(log.substr(0, colon1));
        string event = log.substr(colon1 + 1, colon2 - colon1 - 1);
        int timestamp = stoi(log.substr(colon2 + 1));
        
        if (event == "start") {
            if (!stack.empty()) {
                res[stack.top()] += timestamp - prev;
            }
            stack.push(func_id);
            prev = timestamp;
        } else {
            res[stack.top()] += timestamp - prev + 1;
            stack.pop();
            prev = timestamp + 1;
        }
    }
    
    return res;
}