Problem Description

You have a single-threaded CPU that executes a program with n functions, where each function has a unique ID from 0 to n-1.

The execution follows a call stack pattern:

• When a function starts, its ID is pushed onto the stack
• When a function ends, its ID is popped from the stack
• The function at the top of the stack is the one currently executing

You're given a list of logs where each log entry is formatted as: "{function_id}:{"start" | "end"}:{timestamp}"

For example:

• "0:start:3" means function 0 started at the beginning of timestamp 3
• "1:end:2" means function 1 ended at the end of timestamp 2

Important details:

• Functions can be called multiple times, including recursively
• "Start" logs occur at the beginning of a timestamp
• "End" logs occur at the end of a timestamp

The exclusive time of a function is the total time it spends executing, excluding the time when other functions are executing within it. If a function is called multiple times, its exclusive time is the sum of all its execution times.

Your task is to return an array where the value at index i represents the exclusive time of the function with ID i.

For instance, if function 0 starts at timestamp 0, then function 1 starts at timestamp 2, ends at timestamp 5, and function 0 ends at timestamp 6:

• Function 1's exclusive time is 5 - 2 + 1 = 4 units
• Function 0's exclusive time is (2 - 0) + (6 - 5 - 1 + 1) = 2 + 1 = 3 units (it runs from 0-1, then pauses while function 1 runs, then resumes from 6-6)

Intuition

The key insight is that we need to track which function is currently executing and accumulate time for it whenever another function interrupts or when it completes.

Think of it like a stopwatch for each function. When a function starts, we start its stopwatch. But when another function begins (nested call), we need to pause the current function's stopwatch and start the new one. When the nested function ends, we stop its stopwatch and resume the previous one.

Since functions follow a Last-In-First-Out pattern (the most recently started function must end before its caller can continue), a stack is the natural data structure to track the currently executing functions.

The tricky part is handling the timestamps correctly. Notice that:

• A "start" event happens at the beginning of a timestamp
• An "end" event happens at the end of a timestamp

This means if a function starts at timestamp 3 and ends at timestamp 5, it actually runs during timestamps 3, 4, and 5 - that's 3 time units, not 2. This is why we add 1 when calculating the time for an "end" event.

We maintain a pre variable to track the last processed timestamp. This helps us calculate the time elapsed since the last event:

• When we encounter a new event, we can calculate how much time the currently executing function (top of stack) has been running since pre
• We add this time to that function's exclusive time
• Then we update pre to the current timestamp (or current + 1 for "end" events)

By processing events sequentially and always updating the exclusive time of the function at the top of the stack before handling the current event, we ensure each function gets credited for exactly the time it was actively executing.

Learn more about Stack patterns.

Solution Approach

We implement the solution using a stack to track the currently executing functions and simulate the execution process.

Data Structures:

• stk: A stack to store the IDs of currently executing functions
• ans: An array of size n initialized with zeros to store the exclusive time of each function
• pre: A variable to track the previous timestamp

Algorithm Steps:

1. Initialize the data structures:

   stk = []
   ans = [0] * n
   pre = 0

2. Process each log entry: For each log, we parse it to extract:

   • i: function ID (converted to integer)
   • op: operation type ("start" or "end")
   • cur: current timestamp (converted to integer)

3. Handle "start" operations: When op[0] == "s":

   • If the stack is not empty, there's a function currently executing that needs to be paused
   • Add cur - pre to the exclusive time of the function at the top of the stack (this is the time it ran since the last event)
   • Push the new function ID i onto the stack
   • Update pre = cur (the new function starts at the beginning of this timestamp)

4. Handle "end" operations: When op[0] == "e":

   • The function at the top of the stack is completing
   • Add cur - pre + 1 to its exclusive time (the +1 accounts for the fact that "end" happens at the end of the timestamp)
   • Pop the function from the stack
   • Update pre = cur + 1 (the next timestamp available for the previous function to resume)

Example Walkthrough:

Consider logs: ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]

• Process "0:start:0": Stack becomes [0], pre = 0
• Process "1:start:2":
  • Function 0 ran for 2 - 0 = 2 units, ans[0] = 2
  • Stack becomes [0, 1], pre = 2
• Process "1:end:5":
  • Function 1 ran for 5 - 2 + 1 = 4 units, ans[1] = 4
  • Stack becomes [0], pre = 6
• Process "0:end:6":
  • Function 0 ran for 6 - 6 + 1 = 1 more unit, ans[0] = 2 + 1 = 3
  • Stack becomes empty

Final result: [3, 4]

The time complexity is O(m) where m is the number of logs, and the space complexity is O(n) for the answer array and O(n) for the stack in the worst case.

Example Walkthrough

Let's trace through a small example with 2 functions and the following logs: ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]

Initial State:

• Stack: [] (empty)
• Answer array: [0, 0] (for functions 0 and 1)
• Previous timestamp: 0

Step 1: Process "0:start:0"

• Parse: function ID = 0, operation = "start", timestamp = 0
• Stack is empty, so no function to pause
• Push function 0 onto stack: [0]
• Update previous timestamp: pre = 0

Step 2: Process "1:start:2"

• Parse: function ID = 1, operation = "start", timestamp = 2
• Stack has function 0 on top, which has been running
• Calculate time for function 0: 2 - 0 = 2 units
• Add to function 0's exclusive time: ans[0] = 0 + 2 = 2
• Push function 1 onto stack: [0, 1]
• Update previous timestamp: pre = 2

Step 3: Process "1:end:5"

• Parse: function ID = 1, operation = "end", timestamp = 5
• Function 1 is ending (top of stack)
• Calculate time for function 1: 5 - 2 + 1 = 4 units
  • The +1 accounts for the end happening at the end of timestamp 5
• Add to function 1's exclusive time: ans[1] = 0 + 4 = 4
• Pop function 1 from stack: [0]
• Update previous timestamp: pre = 5 + 1 = 6

Step 4: Process "0:end:6"

• Parse: function ID = 0, operation = "end", timestamp = 6
• Function 0 is ending (top of stack)
• Calculate time for function 0: 6 - 6 + 1 = 1 unit
• Add to function 0's exclusive time: ans[0] = 2 + 1 = 3
• Pop function 0 from stack: [] (empty)
• Update previous timestamp: pre = 6 + 1 = 7

Final Result: [3, 4]

• Function 0 ran exclusively for 3 units (timestamps 0-1, then 6)
• Function 1 ran exclusively for 4 units (timestamps 2-5)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the logs array. Each log entry is processed exactly once in a single pass through the array. The operations performed for each log entry (splitting the string, stack operations like append and pop, and arithmetic operations) all take constant time O(1). Therefore, the overall time complexity is O(n).

The space complexity is O(n). This consists of two main components:

• The ans array which stores the exclusive time for each function, requiring O(n) space where n is the number of functions
• The stk (stack) which in the worst case could contain all function IDs if they are all nested, requiring up to O(n) space

Note that while the problem parameter n represents the number of functions and the reference answer uses n to denote the length of the logs array, the space complexity remains O(n) in both interpretations since the stack size is bounded by the number of functions, and the answer array size equals the number of functions.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding Timestamp Boundaries

The most common pitfall is incorrectly handling the difference between "start" and "end" timestamps:

• "start" occurs at the beginning of a timestamp
• "end" occurs at the end of a timestamp

Incorrect approach:

# Wrong: Treating both start and end the same way
if operation == "end":
    exclusive_times[function_stack.pop()] += current_timestamp - previous_timestamp
    previous_timestamp = current_timestamp  # Wrong!

Why it's wrong: If function A ends at timestamp 5 and function B resumes, function B can start executing from timestamp 6, not timestamp 5. The end timestamp is inclusive.

Correct approach:

if operation == "end":
    exclusive_times[function_stack.pop()] += current_timestamp - previous_timestamp + 1
    previous_timestamp = current_timestamp + 1  # Next available timestamp

2. Forgetting to Update the Currently Running Function

When a new function starts, developers often forget to update the exclusive time of the function that was previously running.

Incorrect approach:

if operation == "start":
    # Wrong: Directly pushing without updating the current function's time
    function_stack.append(function_id)
    previous_timestamp = current_timestamp

Correct approach:

if operation == "start":
    # Update the exclusive time of the currently running function first
    if function_stack:
        exclusive_times[function_stack[-1]] += current_timestamp - previous_timestamp
    function_stack.append(function_id)
    previous_timestamp = current_timestamp

3. Using Wrong Data Type for Parsing

Forgetting to convert string values to integers can lead to incorrect calculations or comparison errors.

Incorrect approach:

function_id, operation, timestamp = log_entry.split(":")
# Using timestamp as string in arithmetic operations
exclusive_times[function_id] += timestamp - previous_timestamp  # Type error!

Correct approach:

function_id, operation, timestamp = log_entry.split(":")
function_id = int(function_id)
current_timestamp = int(timestamp)

4. Off-by-One Error in End Timestamp Calculation

A subtle but critical error is forgetting the +1 when calculating exclusive time for an ending function.

Example to illustrate: If a function starts at timestamp 2 and ends at timestamp 5:

• Wrong calculation: 5 - 2 = 3 units
• Correct calculation: 5 - 2 + 1 = 4 units (it runs during timestamps 2, 3, 4, and 5)

The function executes during the entire duration of timestamp 5, so we need to include that full unit of time.