Teemo Attacking

Difficulty: Easy | Acceptance: 57.70% | Paid: No Topics: Array, Simulation

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: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately. This poisoned status will last 2 seconds until the end of time point 2. And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds. So you finally need to output 4.

Example 2:

Input: timeSeries = [1,2], duration = 2 Output: 3 Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned. This poisoned status will last 2 seconds until the end of time point 2. However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status. Since the poisoned status won’t add up, the total time is 3.

Constraints

- 1 <= timeSeries.length <= 10^4
- 0 <= timeSeries[i], duration <= 10^7
- timeSeries is sorted in non-decreasing order.

Brute Force Simulation

Intuition We can simulate the poison effect by keeping track of every second Ashe is poisoned. We iterate through each attack and mark all seconds from the attack time until the attack time plus duration as “poisoned”. Finally, we count the unique marked seconds.

Steps

• Initialize a set to store unique poisoned seconds.
• Iterate through each attack time in timeSeries.
• For each attack, loop from t to t + duration - 1 and add each second to the set.
• Return the size of the set.

class Solution:
    def findPoisonedDuration(self, timeSeries: list[int], duration: int) -> int:
        poisoned = set()
        for t in timeSeries:
            for i in range(t, t + duration):
                poisoned.add(i)
        return len(poisoned)

Complexity

• Time: O(N * duration) - In the worst case, we iterate through duration seconds for each of the N attacks. This is inefficient for large duration.
• Space: O(N * duration) - To store the set of poisoned seconds.
• Notes: This approach will Time Limit Exceed (TLE) on LeetCode due to large constraints (duration up to 10⁹).

Iterative Comparison

Intuition Instead of tracking every second, we can look at the gap between consecutive attacks. If the time between the current attack and the next attack is greater than or equal to the duration, the full duration counts. If the gap is smaller, only the gap counts because the poison is refreshed by the next attack.

Steps

• If timeSeries is empty, return 0.
• Initialize total to 0.
• Iterate from the first element to the second-to-last element.
• For each element at index i, calculate the difference with the next element: diff = timeSeries[i+1] - timeSeries[i].
• Add min(diff, duration) to total.
• After the loop, add duration to total to account for the full effect of the last attack.
• Return total.

class Solution:
    def findPoisonedDuration(self, timeSeries: list[int], duration: int) -> int:
        if not timeSeries:
            return 0
        total = 0
        n = len(timeSeries)
        for i in range(n - 1):
            diff = timeSeries[i + 1] - timeSeries[i]
            total += min(diff, duration)
        return total + duration

Complexity

• Time: O(N) - We iterate through the array once.
• Space: O(1) - We only use a few variables for storage.
• Notes: This is the optimal approach for this problem.

Tracking End Time

Intuition We can keep track of the moment the current poison effect ends (end). For each new attack at time t, if t is greater than or equal to end, it means the previous poison has worn off, so we add the full duration. If t is less than end, the previous poison is still active, so we only add the overlap (t + duration - end). We then update end to t + duration.

Steps

• Initialize total and end to 0.
• Iterate through each attack time t in timeSeries.
• If t >= end, add duration to total.
• Else, add t + duration - end to total.
• Update end = t + duration.
• Return total.

class Solution:
    def findPoisonedDuration(self, timeSeries: list[int], duration: int) -> int:
        total = 0
        end = 0
        for t in timeSeries:
            if t >= end:
                total += duration
            else:
                total += t + duration - end
            end = t + duration
        return total

Complexity

• Time: O(N) - Single pass through the array.
• Space: O(1) - Constant extra space.
• Notes: This logic is essentially the same as the Iterative Comparison approach but handles the “last element” implicitly.