← DSA Atlas
Dedicated problem page · #636

Exclusive Time of Functions

MediumStack and Expression ProcessingCall-stack simulationStack
Solve on LeetCode ↗
636
MediumStack and Expression ProcessingStackCall-stack simulation

Exclusive Time of Functions

On a single-threaded CPU, n functions run with ids 0..n-1. You are given logs where each entry is "id:start:timestamp" or "id:end:timestamp". A function that starts preempts the currently running one (nested calls). Return an array where the i-th value is the exclusive time of function i — the total time it spent executing on the CPU, not counting time spent inside functions it called.

Open official problem prompt ↗
In plain English

Attribute each unit of CPU time to the exact function that was actually executing at that moment, excluding time spent inside nested calls.

Picture it like this

Like a stopwatch that always times only the person currently speaking in a meeting: when someone interrupts, you note how long the previous speaker held the floor and start timing the interrupter.

Example
Input
n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
Output
[3, 4]
Why
Function 0 runs at times 0-1 (2 units) and 6-6 (1 unit) for 3 total; function 1 runs 2-5 for 4 total.
Constraints
1 <= n <= 1001 <= logs.length <= 5000 <= function id < n0 <= timestamp <= 10^9No two start events and no two end events happen at the same timestampEach function has a matching start/end pair and calls are properly nested
Pattern lesson

See the pattern, then code

Call-stack simulation
Recognition clue

Properly nested start/end events on a single thread are exactly a call stack; the last function to start is the first to end, so a stack models the execution.

↗
Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. Only the function on top of the stack is actually running; whenever a new event occurs, the elapsed time since the previous event is credited to whatever was on top just before this event.

New words, made simpleKnow these before the algorithm
Exclusive time
Time a function itself was on the CPU, not counting time consumed by functions it called.
Inclusive end timestamp
An end event at time t means the function was still running through the whole of unit t, so its duration adds +1.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Interval bookkeeping per function

Extra subtraction logic and quadratic risk make it clumsier than a direct stack.

Track open intervals and subtract child intervals afterward.

Time O(m^2) in the worst caseSpace O(m)
Best choiceSingle-pass call-stack simulation

Directly mirrors how a single-threaded CPU schedules nested calls — clean and linear.

Push on start, pop on end, and credit elapsed time to the current top before each transition.

Time O(m)Space O(n)
The rule we keep true

Invariant

prev is the timestamp at which the currently running function (stack top) most recently gained the CPU, so t - prev is exactly the uncredited slice to award before handling the new event.

Why this is correct

Reasoning

Because calls nest perfectly, the top of the stack is always the one function executing. Every event boundary closes one contiguous running slice; crediting that slice to the top and advancing prev partitions the whole timeline into non-overlapping pieces, each assigned to the function actually running then.

The algorithm in three movesSay these aloud before coding
1Keep a stack of currently active function ids and a prev timestamp

after 1:start:2 -> res[0]+=2, stack=[0,1]

2On a 'start', credit the running top with t - prev, then push the new id and set prev = t

after 1:end:5 -> res[1]+=4, stack=[0]

3On an 'end', credit the popped id with t - prev + 1 (end timestamps are inclusive), then set prev = t + 1

after 0:end:6 -> res[0]+=1, res=[3,4]

4Return the accumulated per-function totals

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
0:start:00
1:start:21
1:end:52
0:end:63
1 · Readstart id 0 at 0
2 · AskAnyone running?
3 · Update statestack=[0], prev=0
4 · ResultNo credit yet; push 0
Key takeaway

Function 1 preempts function 0, then returns control to it.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 9-13Handle start

    Award the previously running top the slice t-prev, then push the new function and reset prev.

  2. 2
    Lines 14-16Handle end

    The +1 accounts for the inclusive end timestamp, and prev jumps to t+1 so the next slice starts after this unit.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single function with no nesting, e.g. one start/end pair
  • Recursion where the same id starts again before ending (still valid nesting)
  • Back-to-back functions where one ends and the sibling starts
  • Large timestamps up to 10^9 (no overflow concern in Python)
!

Common beginner mistakes

  • Forgetting the +1 on end because timestamps are inclusive
  • Setting prev = t instead of t + 1 after an end event
  • Crediting the newly started function instead of the previously running top on a start event
  • Assuming distinct ids per event when recursion can reuse an id
Check your understanding

Why is the duration on an end event t - prev + 1 but on a start event just t - prev?

More in Stack and Expression Processing

#20Valid ParenthesesMatching stack for bracket pairs#71Simplify PathStack of path components#150Evaluate Reverse Polish NotationOperand stack for postfix evaluation#155Min StackStack augmented with running minimum#224Basic CalculatorStack for parenthesized sign context#227Basic Calculator IIStack with deferred multiply/divide