problemeasyalgorithmsleetcode-495leetcode 495leetcode495

Teemo Attacking

EasyUpdated: Oct 13, 2025
Practice on:
LeetCode

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.

Examples

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 <= 10^4
  • 0 <= timeSeries[i], duration <= 10^7
  • timeSeries is sorted in non-decreasing order.

Solution

Method 1 - Interval Non-overlap Accumulation

Intuition

For each attack, if it overlaps with the previous poison, only the non-overlapping part is added. Otherwise, the full duration is added. This ensures no second is double-counted.

Approach

We iterate through the attack times. For each attack, if it does not overlap with the previous poison interval, we add the full duration. If it overlaps, we add only the difference between the current and previous attack times. This ensures we do not double-count overlapping poison times.

Complexity

  • ⏰ Time complexity: O(n) – We iterate through the timeSeries array once.
  • 🧺 Space complexity: O(1) – Only a few integer accumulators are used.

Code

C++
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if (timeSeries.empty() || duration == 0) return 0;
        int total = 0;
        for (size_t i = 0; i < timeSeries.size(); ++i) {
            if (i == 0) {
                total += duration;
            } else {
                int diff = timeSeries[i] - timeSeries[i - 1];
                total += min(duration, diff);
            }
        }
        return total;
    }
};
Go
package solution

func findPoisonedDuration(timeSeries []int, duration int) int {
    if len(timeSeries) == 0 || duration == 0 {
        return 0
    }
    total := 0
    for i := 0; i < len(timeSeries); i++ {
        if i == 0 {
            total += duration
        } else {
            diff := timeSeries[i] - timeSeries[i-1]
            if diff < duration {
                total += diff
            } else {
                total += duration
            }
        }
    }
    return total
}
Java
class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0 || duration == 0) return 0;
        int total = 0;
        for (int i = 0; i < timeSeries.length; i++) {
            if (i == 0) {
                total += duration;
            } else {
                total += Math.min(duration, timeSeries[i] - timeSeries[i-1]);
            }
        }
        return total;
    }
}
Kotlin
class Solution {
    fun findPoisonedDuration(timeSeries: IntArray, duration: Int): Int {
        var total = 0
        for (i in timeSeries.indices) {
            total += if (i == 0) duration else minOf(duration, timeSeries[i] - timeSeries[i-1])
        }
        return total
    }
}
Python
class Solution:
    def findPoisonedDuration(self, timeSeries: list[int], duration: int) -> int:
        total = 0
        for i, t in enumerate(timeSeries):
            if i == 0:
                total += duration
            else:
                total += min(duration, t - timeSeries[i-1])
        return total
Rust
impl Solution {
    pub fn find_poisoned_duration(time_series: Vec<i32>, duration: i32) -> i32 {
        let mut total = 0;
        for i in 0..time_series.len() {
            if i == 0 {
                total += duration;
            } else {
                total += std::cmp::min(duration, time_series[i] - time_series[i-1]);
            }
        }
        total
    }
}
TypeScript
function findPoisonedDuration(timeSeries: number[], duration: number): number {
    let total = 0;
    for (let i = 0; i < timeSeries.length; i++) {
        if (i === 0) {
            total += duration;
        } else {
            total += Math.min(duration, timeSeries[i] - timeSeries[i-1]);
        }
    }
    return total;
}

Comments