# LeetCode 495: Teemo Attacking

## Problem Restatement

Teemo attacks Ashe multiple times.

We are given:

| Input | Meaning |
|---|---|
| `timeSeries` | Times when Teemo attacks |
| `duration` | Poison duration after one attack |

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

| Item | Meaning |
|---|---|
| Input | Integer array `timeSeries`, integer `duration` |
| Output | Total poisoned duration |
| Attack order | `timeSeries` is sorted in non-decreasing order |
| Poison behavior | Overlapping poison intervals merge together |

Function shape:

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

## Examples

Example 1:

```python
timeSeries = [1, 4]
duration = 2
```

Attack at time `1` poisons Ashe during:

```text
[1, 3)
```

Attack at time `4` poisons Ashe during:

```text
[4, 6)
```

These intervals do not overlap.

Total duration:

```text
2 + 2 = 4
```

Answer:

```python
4
```

Example 2:

```python
timeSeries = [1, 2]
duration = 2
```

First attack poisons during:

```text
[1, 3)
```

Second attack poisons during:

```text
[2, 4)
```

These intervals overlap.

The combined poisoned interval is:

```text
[1, 4)
```

Total duration:

```text
3
```

Answer:

```python
3
```

## First Thought: Mark Every Second

One direct idea is to simulate every poisoned second.

For each attack time `t`, mark:

```text
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:

```text
[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:

```text
prev
curr
```

There are two cases.

### No Overlap

If:

```text
curr >= prev + duration
```

then the previous poison fully ends before the next attack.

So the previous attack contributes:

```text
duration
```

seconds.

### Overlap

If:

```text
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:

```text
curr - prev
```

new seconds before the poison resets.

So each attack contributes:

```python
min(duration, curr - prev)
```

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

## Algorithm

Initialize:

```python
total = 0
```

For each consecutive pair of attack times:

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

Add:

```python
min(duration, curr - prev)
```

Finally, add the last attack's full duration:

```python
total + duration
```

## Correctness

Each attack creates a poison interval:

```text
[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:

```text
curr - prev
```

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

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the attack times once |
| Space | `O(1)` | Only a few integer variables are used |

## Implementation

```python
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:

```python
if not timeSeries:
    return 0
```

We scan consecutive attack times:

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

The gap between attacks is:

```python
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:

```python
total += min(duration, curr - prev)
```

Finally, the last attack always contributes the full duration:

```python
return total + duration
```

## Interval Interpretation

Another way to view the problem is interval merging.

Each attack creates:

```text
[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

```python
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:

| Test | Why |
|---|---|
| `[1, 4], 2` | No overlap |
| `[1, 2], 2` | Overlapping intervals |
| `[1], 5` | Single attack |
| `[], 10` | Empty attack list |
| `[1, 2, 3], 2` | Chain overlap |
| `[1, 10], 100` | Large overlap |
| `[1, 1], 2` | Same attack time repeated |