AlgoMaster Logo

Exclusive Time of Functions

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We're simulating a single-threaded CPU that executes functions one at a time. Functions can call other functions, or themselves recursively, which means execution can be interrupted and resumed later. We need to calculate how much time each function spent running, not counting the time when it was paused because a child function was executing.

The word "exclusive" is what makes this tricky. If function 0 runs from time 0 to time 6, but function 1 runs from time 2 to time 5 in the middle, function 0's exclusive time is only 3 (the 2 units before function 1 started and the 1 unit after function 1 ended). Function 1 gets credit for the 4 units it ran.

This is the "self time" that a performance profiler reports for each function: time spent inside the function itself, excluding time spent in functions it called.

The logs come sorted by timestamp, and the call structure is guaranteed to be valid, properly nested like matching parentheses. That nesting is what a stack handles cleanly: a function can only end after every function it called has ended.

Key Constraints:

  • 0 <= timestamp <= 10^9: This is the constraint that drives the design. Timestamps can be up to a billion, so any solution that iterates over individual time units will run far too long. We have to work with the gaps between events, not the time units themselves.
  • 1 <= logs.length <= 500: At most 500 log entries, so a single linear pass over the logs is all we need.
  • 0 <= function_id < n with n <= 100: Function IDs index directly into a small result array.

Approach 1: Stack with Time Tracking (Optimal)

Intuition

Between any two consecutive log events, exactly one function is running: the one on top of the stack. Nothing changes the running function except a start event (which preempts the current one) or an end event (which returns control to the parent). So instead of labeling every time unit, we compute the duration between two events with one subtraction and credit it to whoever was on top.

The stack acts as the call stack of the simulated program. There are two event types to handle:

Start event: A new function preempts the current one. The time since the last event belongs to the function that was on top before this event. Credit that time, then push the new function and update prevTime.

End event: The function on top finishes. The time from the last event through the current timestamp belongs to it. Credit it, pop the stack, and set prevTime to one past the current timestamp.

The asymmetry in the two formulas comes from how the timestamps are defined. A "start" timestamp marks the beginning of a time unit, so the preempted function ran up to but not including that unit (time - prevTime). An "end" timestamp marks the end of a time unit, so the ending function ran through that whole unit (time - prevTime + 1). A function that starts at time 2 and ends at time 5 runs for units 2, 3, 4, 5, which is 5 - 2 + 1 = 4.

A subtle point is why crediting only the top-of-stack function is enough to give every function its correct total, even functions that are paused deep in the stack. A paused function received its credit in the events before it was preempted, and it will receive the remaining credit after the child on top of it ends and control returns. Each segment of real time is credited exactly once, to whichever function was on top during it, so the per-function sums are correct across all the times a function is interrupted and resumed.

Algorithm

  1. Initialize a result array of size n with all zeros.
  2. Initialize an empty stack and set prevTime to 0.
  3. Parse the first log, push its function ID onto the stack, and set prevTime to its timestamp.
  4. For each subsequent log:
    • Parse the function ID, type, and timestamp.
    • If it's a "start" event:
      • Add (timestamp - prevTime) to the result for the function currently on top of the stack.
      • Push the new function ID onto the stack.
      • Set prevTime = timestamp.
    • If it's an "end" event:
      • Add (timestamp - prevTime + 1) to the result for the function on top of the stack.
      • Pop the stack.
      • Set prevTime = timestamp + 1.
  5. Return the result array.

Visualization and Code

Loading animation...