Abstract / Summary

Given function calls with start and end times including recursive calls find the total time each function runs excluding calls to other functions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided exclusiveTime method computes the exclusive execution time for each of n functions based on a sequence of log entries. Each log entry records a function identifier, whether the function started or ended, and a timestamp. The algorithm first orders the logs by timestamp, then walks through them while maintaining a stack of currently active functions. It accumulates time slices for the function on top of the stack, adjusting for the inclusive nature of timestamps, and finally returns the exclusive times for the original n functions.

Key Steps

The first operation orders the log entries to guarantee chronological processing. The sorting key extracts the timestamp component from each log string:

logs.sort(key=lambda x: int(x.split(":")[2]))

A result array exclusive is created with n+1 slots; the extra slot represents a dummy function that runs when the system is idle. The stack active is initialized with this dummy identifier:

exclusive = [0] * (n + 1)
active = [n]

Two helper variables, last and start, track the timestamp of the previously processed log and whether the most recent event was a start, respectively:

last = 0
start = False

The core loop iterates over each sorted log entry, parsing the identifier, event type, and timestamp:

for l in logs:
    id, what, when = l.split(":")
    id = int(id)
    when = int(when)

The elapsed time since the previous log is computed:

duration = when - last

When the current log marks the beginning of a function, the algorithm first adjusts the duration if this is the first start after an idle period, subtracting one to account for the inclusive start timestamp. It then adds the adjusted duration to the exclusive time of the function currently on top of the stack, pushes the new function onto the stack, and records that a start has been seen:

if what == "start":
    if not start:
        duration -= 1
        start = True
    exclusive[active[-1]] += duration
    active.append(id)

When the log indicates a function end, the algorithm reverses the earlier adjustment by adding one to the duration, ensuring the end timestamp is counted. It then adds the corrected duration to the exclusive time of the function that just finished, removes it from the stack, and resets the start flag:

else:
    if start:
        duration += 1
        start = False
    exclusive[id] += duration
    active.pop()

After handling the current log, the last timestamp is updated for the next iteration:

last = when

Finally, the method returns the exclusive times for the original n functions, discarding the dummy entry:

return exclusive[:n]

Edge Cases Handled

The algorithm explicitly introduces a dummy function to represent idle periods, ensuring that time spent when no real function is executing is still accounted for without special-case checks throughout the loop. It also correctly processes consecutive start events by subtracting one from the duration of the first start after idle, thereby preventing double counting of the shared timestamp. Conversely, when an end event follows a start, the algorithm adds one to the duration, guaranteeing that the end timestamp is included in the exclusive time of the finishing function. Nested function calls are naturally handled by the stack: each new start pushes a function identifier, and each end pops it, preserving the proper parent-child relationship. The code also works when there is only a single function, when logs contain only start or only end events (the dummy function absorbs any unmatched intervals), and when timestamps are not initially ordered-the initial sort resolves any disorder.

Performance Optimizations

The implementation uses a plain Python list as a stack (active) with append and pop operations that run in amortized constant time, avoiding the overhead of more complex data structures. The exclusive time array is pre-allocated with the exact required size, eliminating dynamic resizing during accumulation. Parsing of each log entry extracts the three components in a single split call, and integer conversion is performed only for the identifier and timestamp, minimizing repeated work. By adjusting the duration directly within the start and end branches, the algorithm avoids additional conditional branches or separate passes to correct timestamp inclusivity. The initial sort operates on the original list, reusing the existing memory layout and preventing the creation of auxiliary collections. Overall, the design keeps the main loop tight and linear with respect to the number of log entries, ensuring efficient execution even for large inputs.

Imagine a team of little robots working in a workshop. Each robot has an identification number and takes turns doing tasks. This code helps figure out exactly how much time each robot spends working all by itself.

First, the computer organizes all the notes about who started working and who finished working so it can read them in order from the very beginning to the very end. The code creates a special list to keep track of the minutes for every robot. There is also a stack that acts like a busy pile to remember which robot is currently working.

As the computer looks through each note, it breaks the information into smaller pieces to see which robot is involved and at what time the event happens. Because the robots take turns, the computer calculates the time that passes between these events. When a robot starts a task, the computer calculates how long the previous robot was working and adds those minutes to that robot's total. Then the new robot is added to the pile of busy workers. When a robot finishes a task, the computer adds up the time spent and removes that robot from the pile so the next one can take over. The computer keeps doing this over and over until every note has been read and every robot's total time has been counted up.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++		Java
	leetcode.ca	C++	Python	Java				Go		TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fengvyi	C++
	fsq	C++
	gouthampradhan			Java
	halfrost							Go
	JoshCrozier				JS
	linouk23		Python
	lkwq007		Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vli02								C
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
linouk23	Python
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality