# Teemo Attacking
**Difficulty:** EASY
[External](https://leetcode.com/problems/teemo-attacking)
Canonical: https://scaleengineer.com/dsa/problems/teemo-attacking
**Data structures:** Array
**Companies:** [Riot Games](https://scaleengineer.com/companies/riot-games)
---
## Problem
Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly `duration` seconds. More formally, an attack at second `t` will mean Ashe is poisoned during the **inclusive** time interval `[t, t + duration - 1]`. If Teemo attacks again **before** the poison effect ends, the timer for it is **reset**, and the poison effect will end `duration` seconds after the new attack.

You are given a **non-decreasing** integer array `timeSeries`, where `timeSeries[i]` denotes that Teemo attacks Ashe at second `timeSeries[i]`, and an integer `duration`.

Return _the **total** number of seconds that Ashe is poisoned_.

**Example 1:**

**Input:** timeSeries = [1,4], duration = 2
**Output:** 4
**Explanation:** Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

**Example 2:**

**Input:** timeSeries = [1,2], duration = 2
**Output:** 3
**Explanation:** Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 2 however, Teemo attacks again and resets the poison timer. Ashe is poisoned for seconds 2 and 3.
Ashe is poisoned for seconds 1, 2, and 3, which is 3 seconds in total.

**Constraints:**

* `1 <= timeSeries.length <= 104`
* `0 <= timeSeries[i], duration <= 107`
* `timeSeries` is sorted in **non-decreasing** order.

# Approaches
## Brute-Force Simulation using a Set
This approach simulates the poisoning process second by second. We use a data structure, like a `HashSet`, to keep track of every individual second that Ashe is poisoned.
**Time:** O(N * D), where N is the length of `timeSeries` and D is `duration`. We have a nested loop structure where for each of the N attacks, we iterate D times. This is very slow if D is large. · **Space:** O(N * D) in the worst case, where N is the length of `timeSeries` and D is `duration`. The `HashSet` can store up to N * D unique seconds if all poison intervals are disjoint, which can lead to excessive memory usage.
**Pros:** Simple to understand and implement.; Directly models the problem description.
**Cons:** Highly inefficient in terms of both time and space.; Will likely result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error for the given constraints.
### Explanation
We iterate through each attack time `t` in the `timeSeries` array. For each attack, we start a nested loop that runs for `duration` seconds. In this inner loop, we add each second from `t` to `t + duration - 1` into a `HashSet`. The `HashSet` automatically handles duplicates, so if a second is already poisoned, adding it again has no effect. After iterating through all the attacks, the total poisoned time is simply the final size of the `HashSet`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) {
            return 0;
        }
        Set<Integer> poisonedSeconds = new HashSet<>();
        for (int t : timeSeries) {
            for (int i = 0; i < duration; i++) {
                poisonedSeconds.add(t + i);
            }
        }
        return poisonedSeconds.size();
    }
}
```
### Algorithm
- Initialize an empty `HashSet` called `poisonedSeconds`.
- For each attack time `t` in `timeSeries`:
  - Loop from `i = 0` to `duration - 1`.
  - Add `t + i` to the `poisonedSeconds` set.
- Return the size of `poisonedSeconds`.

## Merging Intervals
A more optimized approach is to think in terms of poison intervals instead of individual seconds. Each attack creates a poison interval `[t, t + duration - 1]`. Since the `timeSeries` is sorted, we can process these intervals in order and merge them if they overlap or are contiguous.
**Time:** O(N), where N is the length of `timeSeries`. We iterate through the `timeSeries` once to build the merged intervals and then iterate through the `mergedIntervals` list (which has at most N elements) once to calculate the sum. · **Space:** O(N) in the worst case. If all attacks result in separate, non-overlapping poison intervals, the `mergedIntervals` list will store N intervals.
**Pros:** Much more efficient than the brute-force approach.; Correctly handles all cases by modeling interval merging.
**Cons:** Uses extra space to store the merged intervals, which is not strictly necessary for this problem.
### Explanation
This approach is similar to the classic 'Merge Intervals' problem. We process the attacks sequentially and build a list of consolidated, non-overlapping poison intervals.

We start with an empty list of intervals. For each attack at time `t`, we create a new interval `[t, t + duration - 1]`. We then compare this with the last interval in our list. If the new attack starts after the last poison period has ended, it creates a new, separate interval. If it starts before the last poison period ends, it resets the timer, effectively extending the end time of the last interval. After processing all attacks, we sum the lengths of the intervals in our list to get the total duration.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) {
            return 0;
        }

        List<int[]> mergedIntervals = new ArrayList<>();
        for (int t : timeSeries) {
            int start = t;
            int end = t + duration - 1;

            if (mergedIntervals.isEmpty() || start > mergedIntervals.get(mergedIntervals.size() - 1)[1]) {
                mergedIntervals.add(new int[]{start, end});
            } else {
                mergedIntervals.get(mergedIntervals.size() - 1)[1] = end;
            }
        }

        int totalDuration = 0;
        for (int[] interval : mergedIntervals) {
            totalDuration += interval[1] - interval[0] + 1;
        }
        return totalDuration;
    }
}
```
### Algorithm
- If `timeSeries` is empty, return 0.
- Initialize an empty list of intervals, `mergedIntervals`.
- For each attack time `t` in `timeSeries`:
  - Define the new poison interval as `[start, end]` where `start = t` and `end = t + duration - 1`.
  - If `mergedIntervals` is empty or `start` is greater than the end of the last interval in `mergedIntervals`, add the new interval `[start, end]` to the list.
  - Otherwise, update the end of the last interval in `mergedIntervals` to `end`.
- After the loop, initialize `totalDuration = 0`.
- Iterate through `mergedIntervals` and for each interval `[s, e]`, add `e - s + 1` to `totalDuration`.
- Return `totalDuration`.

## Single Pass with Constant Space
This is the most optimal approach. It builds upon the logic of merging intervals but avoids using any extra space to store the intervals themselves. We can calculate the total poisoned duration in a single pass by considering the time difference between consecutive attacks.
**Time:** O(N), where N is the length of `timeSeries`. We perform a single pass through the array. · **Space:** O(1). We only use a few variables to keep track of the total duration, regardless of the input size.
**Pros:** Optimal solution in terms of both time and space complexity.; Concise and elegant implementation.
**Cons:** The logic might be slightly less intuitive at first glance compared to direct simulation.
### Explanation
We can iterate through the `timeSeries` array and accumulate the total poisoned time in a variable. The key insight is that for any two consecutive attacks, say at `timeSeries[i]` and `timeSeries[i+1]`, the duration of poison contributed by the attack at `timeSeries[i]` is limited by the start of the next attack.

Let's consider the time gap between two attacks: `gap = timeSeries[i+1] - timeSeries[i]`.
- If this `gap` is greater than or equal to the `duration`, it means the poison from the first attack wears off completely before the second attack. In this case, the first attack contributes a full `duration` to the total time.
- If the `gap` is less than the `duration`, it means the second attack happens while the poison is still active, resetting the timer. The actual time Ashe was poisoned between these two attacks is exactly the `gap`.

This logic can be combined into a single expression: for each pair of consecutive attacks, the added duration is `min(duration, timeSeries[i+1] - timeSeries[i])`. We iterate from the first attack to the second-to-last attack, summing up these minimums. Finally, the very last attack in `timeSeries` is not followed by any other attack, so its poison effect will always last for the full `duration`. We must add this final `duration` to our total sum.

```java
class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) {
            return 0;
        }
        
        int totalDuration = 0;
        for (int i = 0; i < timeSeries.length - 1; i++) {
            int diff = timeSeries[i+1] - timeSeries[i];
            totalDuration += Math.min(diff, duration);
        }
        
        // Add the duration for the last attack
        totalDuration += duration;
        
        return totalDuration;
    }
}
```
### Algorithm
- If `timeSeries` is empty, return 0.
- Initialize `totalDuration = 0`.
- Loop from `i = 0` to `timeSeries.length - 2`.
  - Calculate the difference between consecutive attack times: `diff = timeSeries[i+1] - timeSeries[i]`.
  - Add `min(diff, duration)` to `totalDuration`.
- After the loop, add `duration` to `totalDuration` to account for the last attack.
- Return `totalDuration`.

# Solutions
### Python

```python
class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int: ans = duration for a, b in pairwise(timeSeries): ans += min(duration, b - a) return ans

```

### CSharp

```csharp
public class Solution { public int FindPoisonedDuration ( int [] timeSeries , int duration ) { int ans = duration ; int n = timeSeries . Length ; for ( int i = 1 ; i < n ; ++ i ) { ans += Math . Min ( duration , timeSeries [ i ] - timeSeries [ i - 1 ]); } return ans ; } }
```

### Java

```java
class Solution {
public
  int findPoisonedDuration(int[] timeSeries, int duration) {
    int n = timeSeries.length;
    int ans = duration;
    for (int i = 1; i < n; ++i) {
      ans += Math.min(duration, timeSeries[i] - timeSeries[i - 1]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findPoisonedDuration(vector<int> &timeSeries, int duration) {
    int ans = duration;
    int n = timeSeries.size();
    for (int i = 1; i < n; ++i) {
      ans += min(duration, timeSeries[i] - timeSeries[i - 1]);
    }
    return ans;
  }
};

```