{x}
blog image

Teemo Attacking

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

Solution Explanation for Teemo Attacking

This problem involves calculating the total time Ashe is poisoned by Teemo's attacks. The key is understanding that each attack resets the poison timer unless the next attack occurs after the poison effect has ended.

Approach:

The most efficient approach is to iterate through the timeSeries array and accumulate the poisoned time. For each attack, we add the duration to the total poisoned time. However, if the next attack occurs before the current poison effect ends, we only add the time until the next attack. This ensures we don't double-count poisoned time.

Time Complexity Analysis:

The solution iterates through the timeSeries array once. Therefore, the time complexity is O(n), where n is the length of the timeSeries array.

Space Complexity Analysis:

The solution uses a constant amount of extra space. The space complexity is O(1).

Code Explanation (Python):

from itertools import pairwise
 
class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        ans = duration  # Initialize with the duration of the first attack
        for a, b in pairwise(timeSeries): # pairwise is a helpful function from itertools
            ans += min(duration, b - a) # Add the overlap time
        return ans

The pairwise function from the itertools library is used to efficiently iterate through consecutive pairs of elements in timeSeries. This avoids manual indexing.

For each pair (a, b), b - a represents the time difference between consecutive attacks. We take the minimum of this difference and duration to account for cases where the next attack occurs before the poison wears off.

Code in Other Languages:

The logic remains the same across all languages, mainly differing in syntax. The core operation is calculating the minimum time between consecutive attacks and the poison duration to prevent overcounting. The other language examples (Java, C++, Go, TypeScript, C#) all follow this same efficient approach using a single loop and a min function or its equivalent. They all have O(n) time complexity and O(1) space complexity.