LeetCode 495: Teemo Attacking

Problem Restatement

Teemo attacks Ashe multiple times.

We are given:

When Ashe is poisoned, the poison lasts for exactly duration seconds.

If another attack happens before the poison ends, the poison timer resets and continues from the new attack time.

We need to return the total number of seconds Ashe is poisoned.

Input and Output

Function shape:

def findPoisonedDuration(timeSeries: list[int], duration: int) -> int:
    ...

Examples

Example 1:

timeSeries = [1, 4]
duration = 2

Attack at time 1 poisons Ashe during:

[1, 3)

Attack at time 4 poisons Ashe during:

[4, 6)

These intervals do not overlap.

Total duration:

2 + 2 = 4

Answer:

4

Example 2:

timeSeries = [1, 2]
duration = 2

First attack poisons during:

[1, 3)

Second attack poisons during:

[2, 4)

These intervals overlap.

The combined poisoned interval is:

[1, 4)

Total duration:

3

Answer:

3

First Thought: Mark Every Second

One direct idea is to simulate every poisoned second.

For each attack time t, mark:

t, t + 1, ..., t + duration - 1

Then count distinct seconds.

This works, but it is unnecessary and inefficient for large durations.

Key Insight

Each attack creates an interval:

[start, start + duration)

The problem becomes:

Compute the total length of the union of these intervals.

Because the attack times are already sorted, we only need to compare consecutive attacks.

Suppose two consecutive attacks happen at:

prev
curr

There are two cases.

No Overlap

If:

curr >= prev + duration

then the previous poison fully ends before the next attack.

So the previous attack contributes:

duration

seconds.

Overlap

If:

curr < prev + duration

then the next attack starts before the previous poison ends.

The overlap should not be counted twice.

The previous attack contributes only:

curr - prev

new seconds before the poison resets.

So each attack contributes:

min(duration, curr - prev)

except the last attack, which always contributes the full duration.

Algorithm

Initialize:

total = 0

For each consecutive pair of attack times:

prev = timeSeries[i - 1]
curr = timeSeries[i]

Add:

min(duration, curr - prev)

Finally, add the last attack’s full duration:

total + duration

Correctness

Each attack creates a poison interval:

[t, t + duration)

For two consecutive attacks at prev and curr:

If the intervals do not overlap, the previous interval contributes its full length duration.

If the intervals overlap, then the part after curr will already be covered by the next interval. So the previous interval contributes only the non-overlapping portion:

curr - prev

Therefore, the contribution of every interval except the last one is exactly:

min(duration, curr - prev)

The last interval always contributes its full duration because no later attack can overlap it.

Summing these contributions counts every poisoned second exactly once. Thus the algorithm returns the total poisoned duration.

Complexity

Implementation

class Solution:
    def findPoisonedDuration(
        self,
        timeSeries: list[int],
        duration: int,
    ) -> int:
        if not timeSeries:
            return 0

        total = 0

        for i in range(1, len(timeSeries)):
            prev = timeSeries[i - 1]
            curr = timeSeries[i]

            total += min(duration, curr - prev)

        return total + duration

Code Explanation

If there are no attacks, Ashe is never poisoned:

if not timeSeries:
    return 0

We scan consecutive attack times:

for i in range(1, len(timeSeries)):

The gap between attacks is:

curr - prev

If the gap is larger than or equal to duration, there is no overlap.

Otherwise, the overlap reduces the new poisoned time.

This unified formula handles both cases:

total += min(duration, curr - prev)

Finally, the last attack always contributes the full duration:

return total + duration

Interval Interpretation

Another way to view the problem is interval merging.

Each attack creates:

[t, t + duration)

The algorithm incrementally adds only the non-overlapping portion of each interval.

This is why the solution resembles interval union length computation.

Testing

def run_tests():
    s = Solution()

    assert s.findPoisonedDuration([1, 4], 2) == 4
    assert s.findPoisonedDuration([1, 2], 2) == 3
    assert s.findPoisonedDuration([1], 5) == 5
    assert s.findPoisonedDuration([], 10) == 0
    assert s.findPoisonedDuration([1, 2, 3], 2) == 4
    assert s.findPoisonedDuration([1, 10], 100) == 109
    assert s.findPoisonedDuration([1, 1], 2) == 2

    print("all tests passed")

run_tests()

Test meaning: