Teemo Attacking
Problem
Teemo attacks at times in sorted array timeSeries; each attack poisons for duration seconds. Compute the total poisoned time, where overlapping attacks do not double-count.
timeSeries = [1,4], duration = 24def find_poisoned_duration(t, duration):
total = 0
for i in range(len(t) - 1):
total += min(duration, t[i+1] - t[i])
return total + duration if t else 0function findPoisonedDuration(t, duration) {
let total = 0;
for (let i = 0; i < t.length - 1; i++) total += Math.min(duration, t[i+1] - t[i]);
return t.length ? total + duration : 0;
}class Solution {
public int findPoisonedDuration(int[] t, int duration) {
int total = 0;
for (int i = 0; i < t.length - 1; i++) total += Math.min(duration, t[i+1] - t[i]);
return t.length == 0 ? 0 : total + duration;
}
}int findPoisonedDuration(vector<int>& t, int duration) {
int total = 0;
for (int i = 0; i + 1 < (int)t.size(); i++) total += min(duration, t[i+1] - t[i]);
return t.empty() ? 0 : total + duration;
}Explanation
Each attack poisons Teemo's target for duration seconds, but if a new attack lands before the old poison wears off, the overlap should not be counted twice. The neat trick is to look at the gap to the next attack instead of tracking timelines.
For every attack except the last, the poison it contributes is only min(duration, gap), where gap = t[i+1] - t[i]. If the next attack comes after the poison fades, the full duration counts; if it comes sooner, only the time until that next attack counts, because the next attack will pick up from there.
The last attack has no follow-up, so it always adds the full duration. That is why the code sums min(...) over all gaps and then adds one extra duration at the end.
Example: timeSeries = [1,4], duration = 2. The gap is 4 - 1 = 3, so the first attack adds min(2,3) = 2. The last attack adds the full 2. Total = 4.
This is a single pass over the array, so it runs in O(n) time with constant extra space.