Teemo Attacking
EasyPrompt
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 <= 107timeSeriesis sorted in non-decreasing order.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simulates the poisoning process second by second. We use a data structure, like a HashSet, to keep track of every individual second that Ashe is poisoned.
Algorithm
- Initialize an empty
HashSetcalledpoisonedSeconds. - For each attack time
tintimeSeries:- Loop from
i = 0toduration - 1. - Add
t + ito thepoisonedSecondsset.
- Loop from
- Return the size of
poisonedSeconds.
Walkthrough
We iterate through each attack time t in the timeSeries array. For each attack, we start a nested loop that runs for duration seconds. In this inner loop, we add each second from t to t + duration - 1 into a HashSet. The HashSet automatically handles duplicates, so if a second is already poisoned, adding it again has no effect. After iterating through all the attacks, the total poisoned time is simply the final size of the HashSet.
import java.util.HashSet;import java.util.Set; class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { if (timeSeries.length == 0) { return 0; } Set<Integer> poisonedSeconds = new HashSet<>(); for (int t : timeSeries) { for (int i = 0; i < duration; i++) { poisonedSeconds.add(t + i); } } return poisonedSeconds.size(); }}Complexity
Time
O(N * D), where N is the length of `timeSeries` and D is `duration`. We have a nested loop structure where for each of the N attacks, we iterate D times. This is very slow if D is large.
Space
O(N * D) in the worst case, where N is the length of `timeSeries` and D is `duration`. The `HashSet` can store up to N * D unique seconds if all poison intervals are disjoint, which can lead to excessive memory usage.
Trade-offs
Pros
Simple to understand and implement.
Directly models the problem description.
Cons
Highly inefficient in terms of both time and space.
Will likely result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error for the given constraints.
A more optimized approach is to think in terms of poison intervals instead of individual seconds. Each attack creates a poison interval [t, t + duration - 1]. Since the timeSeries is sorted, we can process these intervals in order and merge them if they overlap or are contiguous.
Algorithm
- If
timeSeriesis empty, return 0. - Initialize an empty list of intervals,
mergedIntervals. - For each attack time
tintimeSeries:- Define the new poison interval as
[start, end]wherestart = tandend = t + duration - 1. - If
mergedIntervalsis empty orstartis greater than the end of the last interval inmergedIntervals, add the new interval[start, end]to the list. - Otherwise, update the end of the last interval in
mergedIntervalstoend.
- Define the new poison interval as
- After the loop, initialize
totalDuration = 0. - Iterate through
mergedIntervalsand for each interval[s, e], adde - s + 1tototalDuration. - Return
totalDuration.
Walkthrough
This approach is similar to the classic 'Merge Intervals' problem. We process the attacks sequentially and build a list of consolidated, non-overlapping poison intervals.
We start with an empty list of intervals. For each attack at time t, we create a new interval [t, t + duration - 1]. We then compare this with the last interval in our list. If the new attack starts after the last poison period has ended, it creates a new, separate interval. If it starts before the last poison period ends, it resets the timer, effectively extending the end time of the last interval. After processing all attacks, we sum the lengths of the intervals in our list to get the total duration.
import java.util.ArrayList;import java.util.List; class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { if (timeSeries.length == 0) { return 0; } List<int[]> mergedIntervals = new ArrayList<>(); for (int t : timeSeries) { int start = t; int end = t + duration - 1; if (mergedIntervals.isEmpty() || start > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(new int[]{start, end}); } else { mergedIntervals.get(mergedIntervals.size() - 1)[1] = end; } } int totalDuration = 0; for (int[] interval : mergedIntervals) { totalDuration += interval[1] - interval[0] + 1; } return totalDuration; }}Complexity
Time
O(N), where N is the length of `timeSeries`. We iterate through the `timeSeries` once to build the merged intervals and then iterate through the `mergedIntervals` list (which has at most N elements) once to calculate the sum.
Space
O(N) in the worst case. If all attacks result in separate, non-overlapping poison intervals, the `mergedIntervals` list will store N intervals.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Correctly handles all cases by modeling interval merging.
Cons
Uses extra space to store the merged intervals, which is not strictly necessary for this problem.
This is the most optimal approach. It builds upon the logic of merging intervals but avoids using any extra space to store the intervals themselves. We can calculate the total poisoned duration in a single pass by considering the time difference between consecutive attacks.
Algorithm
- If
timeSeriesis empty, return 0. - Initialize
totalDuration = 0. - Loop from
i = 0totimeSeries.length - 2.- Calculate the difference between consecutive attack times:
diff = timeSeries[i+1] - timeSeries[i]. - Add
min(diff, duration)tototalDuration.
- Calculate the difference between consecutive attack times:
- After the loop, add
durationtototalDurationto account for the last attack. - Return
totalDuration.
Walkthrough
We can iterate through the timeSeries array and accumulate the total poisoned time in a variable. The key insight is that for any two consecutive attacks, say at timeSeries[i] and timeSeries[i+1], the duration of poison contributed by the attack at timeSeries[i] is limited by the start of the next attack.
Let's consider the time gap between two attacks: gap = timeSeries[i+1] - timeSeries[i].
- If this
gapis greater than or equal to theduration, it means the poison from the first attack wears off completely before the second attack. In this case, the first attack contributes a fulldurationto the total time. - If the
gapis less than theduration, it means the second attack happens while the poison is still active, resetting the timer. The actual time Ashe was poisoned between these two attacks is exactly thegap.
This logic can be combined into a single expression: for each pair of consecutive attacks, the added duration is min(duration, timeSeries[i+1] - timeSeries[i]). We iterate from the first attack to the second-to-last attack, summing up these minimums. Finally, the very last attack in timeSeries is not followed by any other attack, so its poison effect will always last for the full duration. We must add this final duration to our total sum.
class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { if (timeSeries.length == 0) { return 0; } int totalDuration = 0; for (int i = 0; i < timeSeries.length - 1; i++) { int diff = timeSeries[i+1] - timeSeries[i]; totalDuration += Math.min(diff, duration); } // Add the duration for the last attack totalDuration += duration; return totalDuration; }}Complexity
Time
O(N), where N is the length of `timeSeries`. We perform a single pass through the array.
Space
O(1). We only use a few variables to keep track of the total duration, regardless of the input size.
Trade-offs
Pros
Optimal solution in terms of both time and space complexity.
Concise and elegant implementation.
Cons
The logic might be slightly less intuitive at first glance compared to direct simulation.
Solutions
Solution
class Solution: def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int: ans = duration for a, b in pairwise(timeSeries): ans += min(duration, b - a) return anspublic class Solution { public int FindPoisonedDuration ( int [] timeSeries , int duration ) { int ans = duration ; int n = timeSeries . Length ; for ( int i = 1 ; i < n ; ++ i ) { ans += Math . Min ( duration , timeSeries [ i ] - timeSeries [ i - 1 ]); } return ans ; } }class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) { int n = timeSeries.length; int ans = duration; for (int i = 1; i < n; ++i) { ans += Math.min(duration, timeSeries[i] - timeSeries[i - 1]); } return ans; }}class Solution {public: int findPoisonedDuration(vector<int> &timeSeries, int duration) { int ans = duration; int n = timeSeries.size(); for (int i = 1; i < n; ++i) { ans += min(duration, timeSeries[i] - timeSeries[i - 1]); } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.