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 thetotal number of seconds that Ashe is poisoned.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

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.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int total = 0;
        for (int i = 0; i < timeSeries.size(); ++i) {
            if (i == 0) {
                total += duration;
            } else {
                total += min(duration, timeSeries[i] - timeSeries[i-1] < 0 ? 0 : timeSeries[i] - timeSeries[i-1]);
                if (timeSeries[i] - timeSeries[i-1] >= duration) total += duration - (timeSeries[i] - timeSeries[i-1]);
            }
        }
        return total;
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        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
1
2
3
4
5
6
7
8
9

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
1
2
3
4
5
6
7
8
9

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
}

Explanation

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.

Complexity

  • ⏰ Time complexity: O(n) where n is the length of timeSeries.
  • 🧺 Space complexity: O(1).