Problem statement

Teemo attacks Ashe at each second listed in the strictly increasing array timeSeries. Every attack poisons Ashe for exactly duration seconds starting at that instant.

If an attack lands while Ashe is already poisoned, the timer resets rather than stacking. Return the total number of seconds Ashe spends poisoned.

Example 1

Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Poisoned during seconds 1-2 and 4-5.

Example 2

Input: timeSeries = [1,2], duration = 2
Output: 3
Explanation: The second attack resets the timer, so the poison covers seconds 1-3.

Example 3

Input: timeSeries = [1,2,3,4,5], duration = 5
Output: 9

Constraints

• 1 <= timeSeries.length <= 100000
• 0 <= timeSeries[i], duration <= 100000000
• timeSeries is strictly increasing.

Hints for Teemo Attacking

1. Hint 1

   Think about how much new poisoned time each attack contributes.

2. Hint 2

   Between consecutive attacks, the earlier one contributes min(duration, gap) seconds.

3. Hint 3

   The very last attack always contributes a full duration.

How to solve Teemo Attacking

Rather than merging intervals, charge each attack for the time it uniquely covers. Attack i is cut short by attack i+1 exactly when the gap between them is smaller than duration.

Approach

1. For each adjacent pair, add min(duration, timeSeries[i] - timeSeries[i-1]).
2. Add a full duration for the final attack, which nothing truncates.
3. Return the sum.

Why it works

The poisoned set is the union of intervals [t_i, t_i + duration). Because the times are strictly increasing, interval i contributes min(duration, t_{i+1} - t_i) before interval i+1 takes over, and the union telescopes into exactly this sum.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Multiplying n * duration ignores overlaps entirely.
• Forgetting the trailing + duration undercounts by one full poison window.
• With values up to 1e8 and 1e5 attacks the total needs 64-bit accumulation in some languages even though the answer fits in 32 bits.

Reference solution

Python

from typing import List

def findPoisonedDuration(timeSeries: List[int], duration: int) -> int:
    if not timeSeries:
        return 0
    total = 0
    for i in range(1, len(timeSeries)):
        gap = timeSeries[i] - timeSeries[i - 1]
        total += gap if gap < duration else duration
    return total + duration

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy