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 {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> rtn(n, 0);
        stack<pair<int, int>> st;  // {function_id, start_time}
        
        for(const string& log: logs) {
            int id = 0, time = 0;
            bool isStart = false;

            // Parse function ID
            int i = 0;
            while(log[i] != ':') {
                id = id * 10 + (log[i] - '0');
                i++;
            }
            i++;
            
            // Parse action (start or end)
            if(log[i] == 's') {
                isStart = true;
                i += 6;  // skip "start"
            } else {
                i += 4;  // skip "end"
            }
            
            // Parse timestamp
            while(i < (int) log.size()) {
                time = time * 10 + (log[i] - '0');
                i++;
            }
            
            if(isStart) {
                // Push function to stack
                st.push({id, time});
            } else {
                // Pop and calculate duration
                auto [funcId, startTime] = st.top();
                st.pop();
                int duration = time - startTime + 1;  // +1 to include end timestamp
                rtn[funcId] += duration;

                // Subtract from parent function
                if(!st.empty()) {
                    rtn[st.top().first] -= duration;
                }
            }
        }
        return rtn;
    }
};

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

// Parse function ID (numeric string to int)
int id = 0;
while(log[i] != ':') {
    id = id * 10 + (log[i] - '0');
    i++;
}

// Check for "start" or "end"
if(log[i + 1] == 's') isStart = true;

Stack Operations

// Start event: push function onto stack
if(isStart) {
    st.push({id, time});
}

// End event: pop and calculate
else {
    auto [funcId, startTime] = st.top();
    st.pop();
    int duration = time - startTime + 1;
    rtn[funcId] += duration;
    
    // Subtract from parent
    if(!st.empty()) {
        rtn[st.top().first] -= duration;
    }
}

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