Abstract / Summary

Teemo attacks every few seconds and poison lasts for a set time; calculate the total time Ashe is poisoned based on attack times and poison duration.

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 58% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Simulation

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 implementation computes the total time a target remains poisoned given a series of attack timestamps and a fixed poisoning duration. It processes the timestamps sequentially, accumulating the effective poisoned interval while correctly handling overlapping periods. The algorithm finishes with a final addition to account for the last poisoning interval.

Key Steps

Initialization

The algorithm begins by storing the first timestamp as the reference point for the previous attack and sets the accumulator for the total poisoned time to zero.

last   = timeSeries[0]
result = 0

Iteration Over Timestamps

For each timestamp in the series the code calculates the contribution of the current attack to the total poisoned duration. The contribution is the smaller of the elapsed time since the previous attack and the fixed duration. This choice automatically caps the contribution when attacks overlap, ensuring that overlapping intervals are not double-counted.

for start in timeSeries:
    result += min(start - last, duration)
    last = start

Final Adjustment

After the loop, the algorithm adds the full duration of the last attack because the loop only accounted for the interval up to the next attack (which does not exist for the final element).

return result + duration

Edge Cases Handled

When the series contains a single timestamp, the loop executes once, adding min(0, duration) which is zero, and the final addition supplies the full duration. This yields the correct total poisoned time for a solitary attack.

If two or more attacks occur within less than the fixed duration, the min function returns the actual gap between attacks, effectively truncating the overlapping portion. Consequently, the total poisoned time reflects a continuous poisoned interval without inflation.

When attacks are spaced farther apart than the duration, the min function returns the full duration, and the algorithm correctly treats each poisoning episode as independent, summing the full durations.

The code also gracefully handles a monotonically increasing timestamp list, which is the expected input shape for this problem.

Performance Optimizations

The solution performs a single linear scan of the input list, updating only two scalar variables. This approach eliminates the need for auxiliary data structures, keeping the memory footprint minimal.

By using the built-in min function, the implementation avoids explicit conditional branches for overlapping versus non-overlapping intervals, allowing the interpreter to execute the comparison efficiently.

The final addition of the duration outside the loop prevents an extra conditional check inside the loop for the last element, simplifying the loop body and reducing per-iteration overhead.

Imagine a little character who is testing out magical glowing mushrooms. Each time the character touches a mushroom, it stays glowing for a specific amount of time. If the character touches a new mushroom before the old one stops glowing, the old one turns off early to make room for the new glow.

The code starts by keeping track of when the character first touched a mushroom. It then walks through the list of every time a new mushroom was touched. For each step, it checks how much time passed since the previous touch. If that time is shorter than the mushroom glow time, it adds that small bit of time to a total counter. If a long time passed, it just adds the full glow time instead. This continues until the very last mushroom is touched, and then one final full glow time is added at the end because that last mushroom gets to shine for its whole life.

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

Time: linear
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++	Python		Java
	leetcode.ca	C++	Python		Java	C#			Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim									C
	everthis			JS
	halfrost								Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	linouk23	C++
	lkwq007		Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	yuanliu666							Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
yuanliu666	Kotlin
YuriSpiridonov	Python
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