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 <= 1040 <= timeSeries[i], duration <= 107timeSeries is sorted in non-decreasing order.In #495 Teemo Attacking, you are given an array timeSeries representing attack times and a fixed duration for the poison effect. Each attack poisons the target for the given duration, but if another attack occurs before the poison ends, the duration overlaps instead of stacking.
The key idea is to simulate the poison timeline. For each attack, compare the time difference between the current attack and the next one. If the gap is smaller than the poison duration, only the gap contributes to the total poisoned time because the effect is refreshed early. Otherwise, the full duration is counted.
By iterating through the array and accumulating the effective poison time, you can compute the total duration. Finally, add the full duration for the last attack. This approach processes each attack once, giving a linear time complexity and constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Array Simulation (Compare Consecutive Attacks) | O(n) | O(1) |
Naresh Gupta
This approach involves iteratively calculating the poison effect duration from the attack times given in timeSeries. The idea is to maintain a running total of poison duration impacts caused by each attack, making adjustments for overlaps where a new attack resets the poison timer.
Time Complexity: O(n), where n is the number of attack times in timeSeries.
Space Complexity: O(1), as we only use a limited amount of extra space.
1#include <stdio.h>
2
3int findPoisonedDuration(int* timeSeries, int timeSeriesSize, int duration) {
4 int totalDuration = 0;
5
The solution iterates over the array, and for each attack time, it calculates the increment to the total poison duration. If the next attack occurs after the current poison effect ends, it simply adds the full duration. Otherwise, it adds only the period from the current attack time to the next one (since next attack resets the poison).
In this approach, we utilize a dynamic programming technique to handle overlapping intervals. The essence here is to consider the overlap between poison effects and adjust the ending intervals of these periods dynamically.
Time Complexity: O(n) since we iterate through timeSeries just once.
Space Complexity: O(1) due to using minimal additional memory.
1using System;
2
public class TeemoAttacking {
public int FindPoisonedDuration(int[] timeSeries, int duration) {
if (timeSeries.Length == 0) return 0;
int totalDuration = 0;
int end = timeSeries[0] + duration;
for (int i = 1; i < timeSeries.Length; ++i) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i - 1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration;
return totalDuration;
}
public static void Main(string[] args) {
TeemoAttacking ta = new TeemoAttacking();
int[] timeSeries = {1, 4};
int duration = 2;
Console.WriteLine(ta.FindPoisonedDuration(timeSeries, duration));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like Teemo Attacking appear in coding interviews because they test array traversal, interval reasoning, and edge case handling. While not always the exact question, similar interval or simulation problems are common in FAANG-style interviews.
An array is sufficient since the attack times are already provided in sorted order. The problem mainly requires sequential comparison between adjacent elements, so no additional complex data structures are needed.
The optimal approach is to iterate through the attack times and compare the gap between consecutive attacks. For each pair, add the minimum of the gap and the poison duration to the total time. This avoids double counting overlapping poison intervals and runs in linear time.
If the next attack happens before the poison expires, the previous poison is effectively cut short and refreshed. Using the minimum ensures that overlapping durations are not counted twice while still capturing the effective poisoned time.
This C# solution leverages updating end times dynamically, accounting for overlaps and sequential attacks. It calculates the total poisoned time efficiently.