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.Problem Overview: You are given an array timeSeries where each value represents the second when Teemo attacks Ashe. Every attack poisons Ashe for duration seconds. If another attack happens before the poison ends, the timer resets. The task is to compute the total time Ashe remains poisoned.
Approach 1: Iterative Calculation of Poison Duration (O(n) time, O(1) space)
This approach scans the attack timeline once and calculates how much poison each attack contributes. For two consecutive attacks at timeSeries[i] and timeSeries[i+1], compute the gap between them. If the gap is smaller than duration, the poison overlaps and only the gap contributes. If the gap is larger, the full duration is added. In practice, you iterate through the array and accumulate min(duration, timeSeries[i+1] - timeSeries[i]) for each pair, then add one final duration for the last attack. This works because overlapping intervals never need to be merged explicitly; the difference between timestamps already tells you the extra poisoned time. The approach is simple, linear, and uses constant memory. It relies only on sequential traversal of the array and direct arithmetic comparisons.
Approach 2: Dynamic Programming with Overlapping Intervals (O(n) time, O(1) space)
This method treats the problem as a sequence of overlapping intervals. Each attack creates an interval [timeSeries[i], timeSeries[i] + duration). The DP idea tracks the end of the previous poison interval and decides whether the current attack overlaps with it. If the new attack occurs after the previous poison ends, add the full duration. If it occurs before the previous poison expires, only add the extension beyond the current end. The state you maintain is simply the end time of the active poison window. During iteration, update the end boundary and accumulate the additional poisoned seconds. Conceptually this resembles interval merging and fits naturally into problems involving simulation or dynamic programming over time-based states.
Recommended for interviews: The iterative calculation approach is what most interviewers expect. It demonstrates that you recognize the overlapping interval pattern and reduce it to a simple difference calculation. The DP-style interval tracking also works and helps if you think in terms of interval merging, but the direct iteration with min(duration, gap) is the cleanest and most commonly discussed solution.
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.
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).
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.
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.
This C solution manages the end of the current poison effect period, adjusting it dynamically with each attack. It checks for overlapped periods and updates the total duration based on effective poisoning time.
Time Complexity: O(n) since we iterate through timeSeries just once.
Space Complexity: O(1) due to using minimal additional memory.
| Approach | Complexity |
|---|---|
| Iterative Calculation of Poison Duration | Time Complexity: O(n), where n is the number of attack times in |
| Dynamic Programming with Overlapping Intervals | Time Complexity: O(n) since we iterate through |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Calculation of Poison Duration | O(n) | O(1) | Best general solution when attacks are processed sequentially |
| Dynamic Programming with Overlapping Intervals | O(n) | O(1) | Useful when thinking in terms of interval extension or state tracking |
teemo attacking | teemo attacking leetcode | leetcode 495 | java python3 c++ • Naresh Gupta • 3,497 views views
Watch 9 more video solutions →Practice Teemo Attacking with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor