LeetCode 495 - Teemo Attacking

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

The problem asks us to calculate the total duration that Ashe is poisoned by Teemo's attacks. Each attack at a given second t causes Ashe to be poisoned for exactly duration seconds, and the poisoning time is inclusive, meaning that the poison effect lasts from time t to t + duration - 1. If Teemo attacks again before the poison from a previous attack has ended, the poison timer is reset, which means the poison duration effectively overlaps but does not double count the time.

The input is a non-decreasing array timeSeries of integers, each representing a second when Teemo attacks, and an integer duration representing how long a single attack poisons Ashe. The output is a single integer representing the total number of seconds Ashe remains poisoned, taking into account overlapping attacks.

Constraints inform us that timeSeries can have up to 10^4 elements and values can be as large as 10^7, which means any solution that iterates over every single second of poison for each attack could be inefficient. The guarantee that timeSeries is sorted allows us to consider sequential comparisons between attacks without needing to sort first. Important edge cases include attacks occurring at the same second, duration being zero, and only one attack being present.

Approaches

A brute-force approach would be to simulate each second Ashe is poisoned, marking every second in a set or boolean array, then summing all poisoned seconds. While this works, it is inefficient because if duration is large and attacks are sparse, iterating over every second could result in a high runtime.

The optimal approach relies on observing that overlapping poison durations should only count the non-overlapping part of each new attack. For each attack after the first, we calculate the gap between the current attack time and the end of the previous poison effect. If the gap is greater than or equal to the duration, the full duration is added. If the gap is smaller, only the gap counts toward new poisoned time, since the remaining seconds are already included in the previous attack’s poison interval. This allows a single pass through the array without simulating each second individually.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * duration)	O(n * duration)	Iterates over each second of poison for each attack, inefficient for large duration
Optimal	O(n)	O(1)	Computes non-overlapping poison time in one pass, minimal extra space

Algorithm Walkthrough

Initialize a variable total_poisoned to 0 to accumulate the total poisoned seconds.
Initialize end_time to 0. This variable will track the second when the current poison effect ends.
Iterate over each attack time t in timeSeries.
For each t, calculate the effective poisoned time contributed by this attack. If t is greater than or equal to end_time, the poison from this attack does not overlap with previous poison, so add the full duration to total_poisoned. Otherwise, add the difference t + duration - end_time to account for only the new poisoned seconds.
Update end_time to t + duration, the end of the poison effect from this attack.
After processing all attacks, return total_poisoned.

This algorithm works because the invariant it maintains is that end_time always tracks the farthest second that Ashe is poisoned. By only adding non-overlapping poison intervals, we ensure that each second is counted exactly once.

Python Solution

from typing import List

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        if not timeSeries or duration == 0:
            return 0
        
        total_poisoned = 0
        end_time = 0
        
        for t in timeSeries:
            if t >= end_time:
                total_poisoned += duration
            else:
                total_poisoned += t + duration - end_time
            end_time = t + duration
        
        return total_poisoned

In this implementation, we first handle the edge case where the attack list is empty or the duration is zero, immediately returning 0. We then iterate over each attack time. For non-overlapping attacks, we add the full duration. For overlapping attacks, we add only the portion not already covered by the previous poison interval. Finally, we update end_time after each attack to represent the end of the current poison effect.

Go Solution

func findPoisonedDuration(timeSeries []int, duration int) int {
    if len(timeSeries) == 0 || duration == 0 {
        return 0
    }
    
    totalPoisoned := 0
    endTime := 0
    
    for _, t := range timeSeries {
        if t >= endTime {
            totalPoisoned += duration
        } else {
            totalPoisoned += t + duration - endTime
        }
        endTime = t + duration
    }
    
    return totalPoisoned
}

In Go, we similarly handle edge cases upfront. The loop logic mirrors the Python solution, using integer arithmetic to compute the non-overlapping poison duration. Go’s slices and range loops make this straightforward, and the endTime variable tracks the poison effect exactly as in Python.

Worked Examples

Example 1: timeSeries = [1,4], duration = 2

Attack	end_time before attack	Poison added	end_time after attack	total_poisoned
1	0	2	3	2
4	3	2	6	4

Example 2: timeSeries = [1,2], duration = 2

Attack	end_time before attack	Poison added	end_time after attack	total_poisoned
1	0	2	3	2
2	3	1	4	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the `timeSeries` array once, performing constant-time calculations per element.
Space	O(1)	Only a few integer variables are used; no extra data structures proportional to input size.

Because we avoid simulating each second of poison, the solution is efficient even for large durations and long input arrays.

Test Cases

# Provided examples
assert Solution().findPoisonedDuration([1,4], 2) == 4  # overlapping intervals non-existent
assert Solution().findPoisonedDuration([1,2], 2) == 3  # overlapping intervals

# Edge cases
assert Solution().findPoisonedDuration([], 5) == 0  # empty input
assert Solution().findPoisonedDuration([5], 0) == 0  # zero duration
assert Solution().findPoisonedDuration([1,2,3,4], 1) == 4  # duration of 1 second per attack
assert Solution().findPoisonedDuration([1,1,1], 2) == 2  # multiple attacks at the same second
assert Solution().findPoisonedDuration([1,3,5,7], 10) == 16  # long duration overlapping multiple attacks

Test	Why
`[1,4], 2`	Checks standard non-overlapping intervals
`[1,2], 2`	Checks overlapping intervals
`[], 5`	Handles empty input edge case
`[5], 0`	Handles zero duration
`[1,2,3,4], 1`	Tests minimal duration per attack
`[1,1,1], 2`	Tests multiple attacks at the same second
`[1,3,5,7], 10`	Tests large duration causing overlapping intervals

Edge Cases

Empty attack list: When timeSeries is empty, the algorithm must immediately return 0. This prevents unnecessary computation and ensures no errors occur due to accessing elements in an empty list.
Zero duration attacks: If duration is 0, Ashe is poisoned for no time regardless of attack times. The implementation handles this by checking duration == 0 upfront and returning 0.
Overlapping attacks at the same second: If multiple attacks occur at the same second, the poison duration should not double count. The implementation correctly adds only the first attack’s full duration and treats subsequent attacks as overlapping, contributing zero extra seconds. This is managed through the calculation t + duration - end_time, which becomes zero for repeated attacks at the same second.