Difficulty: Medium
Category: Stack, Parsing, Simulation
Companies: Amazon, Facebook, Google, Twitter

On a single-threaded CPU, we can only execute one function at a time. When a function call starts, it’s recorded with a start timestamp. When a call ends, it’s recorded with an end timestamp. Functions can call other functions, creating a call stack.

Given an integer n representing the number of functions, and an array logs, where logs[i] represents the i-th log message formatted as "{function_id}:{"start"|"end"}:{timestamp}", return an array where each element is the exclusive time of that function.

Exclusive time is the sum of execution times for all calls to a function, excluding time spent calling other functions.

Examples

Example 1:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]
Explanation:
- Function 0 starts at 0 and ends at 6, taking 6 units total
- Function 0 calls function 1, which runs from 2 to 5 (3 units)
- Function 0 exclusive time: 6 - 3 = 3 units
- Function 1 exclusive time: 5 - 2 + 1 = 4 units (inclusive of end timestamp)

Example 2:

Input: n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:end:6"]
Output: [3]
Explanation:
- First call: starts at 0, second call starts at 2
- Second call ends at 5 (duration 4)
- First call ends at 6 (duration 7 total, minus 4 from nested call = 3)

Example 3:

Input: n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
Output: [4,1]
Explanation:
- Function 0: recursive calls from 0-5 (3 units) + 6-7 (1 unit) = 4 total
- Function 1: runs at timestamp 6 (1 unit)

Constraints

  • 1 <= n <= 100
  • 1 <= logs.length <= 500
  • 0 <= function_id < n
  • 0 <= timestamp <= 10^9
  • No two start events will happen at the same timestamp
  • No two end events will happen at the same timestamp
  • Each function call has a matching start and end event

Solution Approaches

Key Insight: Use a stack to track the current call stack. When a function starts, push it. When it ends, calculate its duration and subtract that time from its parent.

Algorithm:

  1. Parse each log entry to extract function ID, action (start/end), and timestamp
  2. Maintain a stack of active function calls
  3. When a function starts: push to stack
  4. When a function ends:
    • Pop the top function and calculate its duration
    • Add duration to the function’s exclusive time
    • Subtract duration from the parent function (if exists) in the stack

Time Complexity: O(m) where m is the number of logs
Space Complexity: O(n) for the stack

class Solution:
    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:
        result = [0] * n
        st = []  # stack of function ids
        prev_time = 0

        for log in logs:
            func_id, action, timestamp = log.split(':')
            func_id = int(func_id)
            timestamp = int(timestamp)

            if action == 'start':
                # If another function is running, add time to it
                if st:
                    result[st[-1]] += timestamp - prev_time
                st.append(func_id)
                prev_time = timestamp

            else:
                # End current function
                result[st.pop()] += timestamp - prev_time + 1
                prev_time = timestamp + 1

        return result

Solution Explanation

Approach: Monotonic stack (this problem)

Key idea: Difficulty:** Medium

How the code works: Difficulty: Medium Category: Stack, Parsing, Simulation

  • Stack matches nested or LIFO structure (parentheses, monotonic scans).
  • Push on open / larger; pop when the current element resolves pending work.
  • Monotonic stack finds next greater/smaller in O(n).

Walkthrough — input n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"], expected output [3,4]:

  • Function 0 starts at 0 and ends at 6, taking 6 units total
  • Function 0 calls function 1, which runs from 2 to 5 (3 units)
  • Function 0 exclusive time: 6 - 3 = 3 units
  • Function 1 exclusive time: 5 - 2 + 1 = 4 units (inclusive of end timestamp)

    Implementation Details

Manual String Parsing

class Solution:
    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:
        result = [0] * n
        st = []
        prev_time = 0

        for log in logs:
            parts = log.split(':')
            func_id = int(parts[0])
            is_start = (parts[1] == "start")
            timestamp = int(parts[2])

            if is_start:
                if st:
                    result[st[-1][0]] += timestamp - prev_time
                st.append((func_id, timestamp))
                prev_time = timestamp
            else:
                funcId, startTime = st.pop()
                result[funcId] += timestamp - prev_time + 1
                prev_time = timestamp + 1

        return result

Stack Operations

class Solution:
    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:
        result = [0] * n
        st = []  # stack of function IDs
        prevTime = 0

        for log in logs:
            func_id, action, timestamp = log.split(':')
            func_id = int(func_id)
            timestamp = int(timestamp)

            if action == "start":
                # If a function is already running, add time to it
                if st:
                    result[st[-1]] += timestamp - prevTime

                st.append(func_id)
                prevTime = timestamp

            else:
                # End current function
                result[st.pop()] += timestamp - prevTime + 1
                prevTime = timestamp + 1

        return result

Edge Cases

  1. Single Function: Only one function, no nesting → straightforward timing
  2. Recursive Calls: Same function called recursively → handled by stack
  3. Multiple Separate Calls: Same function called at different times → duration summed
  4. Immediate Returns: Start and end at same timestamp → duration = 1
  5. Deep Nesting: Multiple levels of function calls → stack maintains hierarchy

Follow-up Questions

  • What if logs could be out of order?
  • How would you handle multi-threaded execution?
  • What if you needed to track inclusive time instead?
  • How would you detect mismatched start/end events?

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Optimization Techniques

  1. Stack for Hierarchy: Perfect data structure for call stack modeling
  2. Subtraction Trick: Efficient way to calculate exclusive time
  3. Inclusive Counting: End timestamp included in duration calculation
  4. Parent Tracking: Stack automatically maintains parent information

Code Quality Notes

  1. Readability: Approach 1 with manual parsing is most educational
  2. Maintainability: Approach 2 with stringstream is cleaner
  3. Performance: All approaches are O(n) time and space
  4. Correctness: Key insight is the subtraction from parent

This problem elegantly demonstrates how to model a call stack using a stack data structure and calculate exclusive time by tracking parent-child relationships in function calls.

Key Takeaways

  • Pattern: Monotonic stack (this problem)
  • Difficulty:** Medium
  • Category:** Stack, Parsing, Simulation

References

Template Reference

Thinking Process

Difficulty: Medium

Category: Stack, Parsing, Simulation

  • Stack matches nested or LIFO structure (parentheses, monotonic scans).
  • Push on open / larger; pop when the current element resolves pending work.
  • Monotonic stack finds next greater/smaller in O(n).
Stack top push / pop LIFO — monotonic stack scans array

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Monotonic stack (this problem) O(n) O(n) Next greater/smaller element
Parentheses matching O(n) O(n) Push open, pop on close
Expression evaluation O(n) O(n) Operand + operator stacks
Stack simulation O(n) O(n) Process in LIFO order