495. Teemo Attacking #

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.

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

Problem Summary #

In the world of League of Legends, there is a champion named “Teemo”. His attacks can put the enemy champion Ashe (editor’s note: the Frost Archer) into a poisoned state.

When Teemo attacks Ashe, Ashe’s poisoned state lasts exactly duration seconds.

More formally, an attack by Teemo at time t means Ashe is poisoned during the time interval [t, t + duration - 1] (including t and t + duration - 1).

If Teemo attacks again before the poison effect ends, the poison state timer will be reset, and after the new attack, the poison effect will end after duration seconds.

You are given a non-decreasing integer array timeSeries, where timeSeries[i] means Teemo attacks Ashe at second timeSeries[i], and an integer duration representing the poison duration.

Return the total number of seconds that Ashe is in the poisoned state.

Solution Approach #

• Start counting i from 1, and let t be equal to timeSeries[i - 1]
• Compare end(t + duration - 1) with timeSeries[i],
  • If end is less than timeSeries[i], ans+=duration
  • Otherwise ans += timeSeries[i] - t
• ans += duration and return ans

Code #

package leetcode

func findPoisonedDuration(timeSeries []int, duration int) int {
	var ans int
	for i := 1; i < len(timeSeries); i++ {
		t := timeSeries[i-1]
		end := t + duration - 1
		if end < timeSeries[i] {
			ans += duration
		} else {
			ans += timeSeries[i] - t
		}
	}
	ans += duration
	return ans
}