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 int[] exclusiveTime(int n, String[] logs) {
        int[] rtn = new int[n];
        stack<int[]> st;  // new int[] {function_id, start_time}

        for(String log: logs) {
            int id = 0, time = 0;
            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.offer(new int[] {id, time});
            } else {
                // Pop and calculate duration
                int[] funcIdpair = st.peek(); int funcId = funcIdpair[0]; int startTime = funcIdpair[1];
                st.poll();
                int duration = time - startTime + 1;  // +1 to include end timestamp
                rtn.put(funcId, rtn.getOrDefault(funcId, 0) + duration;

                // Subtract from parent function
                if(!st.isEmpty()) {
                    rtn[st.peek().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

class Solution {
    public int[] exclusiveTime(int n, String[] logs) {
        int[] rtn = new int[n];
        stack<int[]> st;

        for(String log: logs) {
            stringstream ss = new stringstream(log);
        String token;

            // Parse ID getline = new ID(ss, token, ':');
            int id = Integer.parseInt(token);

            // Parse action getline = new action(ss, token, ':');
            boolean isStart = (token == "start");

            // Parse timestamp getline = new timestamp(ss, token, ':');
            int time = Integer.parseInt(token);

            if(isStart) {
                st.offer(new int[] {id, time});
            } else {
                int[] funcIdpair = st.peek(); int funcId = funcIdpair[0]; int startTime = funcIdpair[1];
                st.poll();
                int duration = time - startTime + 1;
                rtn.put(funcId, rtn.getOrDefault(funcId, 0) + duration;

                if(!st.isEmpty()) {
                    rtn[st.peek().first] -= duration;
                }
            }
        }
        return rtn;
    }
}

Stack Operations

// import java.util.*;
class Solution {
    public int[] exclusiveTime(int n, String[] logs) {
        int[] rtn = new int[n];
        Deque<Integer> st = new ArrayDeque<>();  // Only store function IDs
        int prevTime = 0;
        for(String log: logs) {
            stringstream ss = new stringstream(log);
            String token;

            getline(ss, token, ':');
            int id = Integer.parseInt(token);

            getline(ss, token, ':');
            boolean isStart = (token == "start");

            getline(ss, token, ':');
            int time = Integer.parseInt(token);

            if(isStart) {
                if(!st.isEmpty()) {
                    rtn[st.peek()] += time - prevTime;
                }
                st.offer(id);
                prevTime = time;
            } else {
                rtn[st.peek()] += time - prevTime + 1;
                st.poll();
                prevTime = time + 1;
            }
        }
        return rtn;
    }
}

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