Problem Description

In the "Teemo Attacking" problem, you are given an integer array timeSeries representing the times at which Teemo attacks an enemy, and an integer duration representing how long each attack's poison effect lasts. When Teemo attacks at time t, the enemy is poisoned from time t up to but not including time t + duration.

If another attack happens before the previous poison effect ends, the poison timer resets, but overlapping poison durations should not be double-counted.

Your task is to calculate the total time the enemy is poisoned.

• Input: timeSeries (List of integers), duration (integer)
• Output: Integer representing the total poisoned duration
• Constraints:
  • 1 ≤ timeSeries.length ≤ 10⁴
  • 0 ≤ timeSeries[i], duration ≤ 10⁷
  • timeSeries is sorted in non-decreasing order

Thought Process

To solve this problem, let's first consider the brute-force approach: for each attack, we could mark every second the enemy is poisoned, but this quickly becomes inefficient for large inputs.

The key insight is that poison durations can overlap. If two attacks are spaced apart by less than duration, the second attack's poison effect starts before the first one ends, so their poison durations overlap. Instead of counting the full duration for both, we should only count the non-overlapping part.

Therefore, for each attack (except the last), the actual poison time contributed is the minimum of duration and the gap to the next attack. The last attack always contributes duration since nothing comes after it.

Solution Approach

• Step 1: Initialize a variable, say total, to keep track of the total poisoned time.
• Step 2: Loop through the timeSeries array. For each attack except the last:
  • Calculate the time difference to the next attack: gap = timeSeries[i+1] - timeSeries[i]
  • The poison effect from this attack is min(duration, gap)
  • Add this value to total
• Step 3: After the loop, add duration for the last attack (since it always contributes its full duration).
• Step 4: Return total as the result.

This approach is efficient, requiring only a single pass through the input array.

Example Walkthrough

Let's use timeSeries = [1, 4] and duration = 2 as an example.

• Attack at time 1: poisons from 1 to 3.
• Attack at time 4: poisons from 4 to 6.
• The gap between attacks is 3 (4 - 1), which is greater than duration, so there's no overlap.
• Total poison time: 2 (first attack) + 2 (second attack) = 4

Now, consider timeSeries = [1, 2] and duration = 2:

• Attack at time 1: poisons from 1 to 3.
• Attack at time 2: poisons from 2 to 4.
• The gap is 1 (2 - 1), so the second attack starts before the first ends.
• First attack contributes min(2, 1) = 1.
• Second (last) attack always contributes 2.
• Total poison time: 1 + 2 = 3

Time and Space Complexity

• Brute-force approach: If we marked each poisoned second, the time complexity would be O(N * D), where N is the number of attacks and D is the duration. This is not efficient for large inputs.
• Optimized approach: We process each attack once, so time complexity is O(N).
• Space complexity: O(1), since we only use a few variables for counting. We do not need any extra data structures proportional to input size.

Summary

The "Teemo Attacking" problem is a great example of how careful analysis of overlapping intervals can lead to an efficient solution. By considering only the non-overlapping portions of each attack's poison effect and always adding the full duration for the last attack, we achieve a one-pass, O(N) solution. This approach avoids unnecessary work and elegantly handles all cases, including overlapping and non-overlapping attacks.

Code Implementation

class Solution:
    def findPoisonedDuration(self, timeSeries, duration):
        if not timeSeries:
            return 0
        total = 0
        for i in range(len(timeSeries) - 1):
            gap = timeSeries[i+1] - timeSeries[i]
            total += min(duration, gap)
        total += duration
        return total
      

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if (timeSeries.empty()) return 0;
        int total = 0;
        for (int i = 0; i < timeSeries.size() - 1; ++i) {
            int gap = timeSeries[i+1] - timeSeries[i];
            total += min(duration, gap);
        }
        total += duration;
        return total;
    }
};
      

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) return 0;
        int total = 0;
        for (int i = 0; i < timeSeries.length - 1; i++) {
            int gap = timeSeries[i+1] - timeSeries[i];
            total += Math.min(duration, gap);
        }
        total += duration;
        return total;
    }
}
      

var findPoisonedDuration = function(timeSeries, duration) {
    if (timeSeries.length === 0) return 0;
    let total = 0;
    for (let i = 0; i < timeSeries.length - 1; i++) {
        let gap = timeSeries[i+1] - timeSeries[i];
        total += Math.min(duration, gap);
    }
    total += duration;
    return total;
};