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.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).
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 |
teemo attacking | teemo attacking leetcode | leetcode 495 | java python3 c++ • Naresh Gupta • 3,242 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