495 Teemo Attacking

1. Description

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 inclusive time terminal [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 ar 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.

 

constraints :

• 1 <= timeSeries.length <= 104
• 0 <= timeSeries[i], duration <= 107
• timeSeries is sorted in non-decreasing order.

2. Algorithms

There are three conditions we need to consider :

1. Each timeSeries[i] have duration which is stored in duration input.
2. For each i, i have interval [timeSeries[i], timeSeries[i] + duration - 1].

Let's see when timeSeries is [1, 2, 5, 6] and duration is 2. Then, each timeSeries[i] have 2 duration seperately. So our total duration will be 2 + 2 + 2 + 2 = 8. However, there are interval in each timeSeries[i].

• i = 0, timeSeries[0] = 1, interval = [1, 2]
• i = 1, timeSeries[1] = 2, interval = [2, 3]
• i = 2, timeSeries[2] = 5, interval = [5, 6]
• i = 2, timeSeries[3] = 6, interval = [6, 7]

There are two intersection between [1, 2] and [5, 6]. So our total duration will be 2 + (2 - 1) + 2 + (2 - 1) = 6. Let's think about when duration is 3.

• i = 0, timeSeries[0] = 1, interval = [1, 3]
• i = 1, timeSeries[1] = 2, interval = [2, 4]
• i = 2, timeSeries[2] = 5, interval = [5, 7]
• i = 3, timeSeries[3] = 6, interval = [6, 8]

In case of duration = 3, total duration will be 3 + (3 - 2) + 3 + (3 - 2) = 8.

 

So when we meet new timeSeries, we add duration to our total duration. If last element of previous interval is bigger than current timeSeries, add (duration - (prev - current + 1)).

 

1. Start
2. Declare variables poisoned, prev initialized with 0.
3. Repeat steps through elements of timeSeries.
   1. Add duration to poisoned.
   2. If prev is greater than and equal to current value, minus (prev - timeSeries[i] + 1) from poisoned.
   3. Store timeSeries[i] + duration - 1 to variable named prev.
4. Return result of poisoned
5. End

3. Codes

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        poisoned, prev = 0, -1
        
        for i in range(len(timeSeries)) : 
            poisoned += duration 
            
            if prev >= timeSeries[i] : 
                poisoned -= (prev - timeSeries[i] + 1)
                
            prev = timeSeries[i] + duration - 1
            
        return poisoned

 

4. Conclusion