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 <= 104
- 0 <= timeSeries[i], duration <= 107
- timeSeries is sorted in non-decreasing order.
My Solution
We can solve this problem by keeping track of the timestamp at which Ashe is poisoned. We iterate the array and keep track of the timestamp by adding duration-1 to current element of timeSeries. If the next element of timeSeries is less than or equal to this timestamp, we just add the difference between the two elements in timeSeries, since Teemo attacked again before the last attack could have full effect. Otherwise, the attack could run fully, so we just add duration to our total poisoned time. We update our timestamp at every iteration. Finally the last attack runs for the full duration so we just add duration to our total in the end.
Time complexity is O(n), where n is the length of timeSeries, because we iterate through the array once. Space complexity is O(1) since we only require constant extra space.
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int time = timeSeries[0] + duration - 1;
int total = 0;
int n = timeSeries.length;
for (int i = 1; i < n; i++) {
if (timeSeries[i] > time) {
total += duration;
}
else {
total += (timeSeries[i] - timeSeries[i-1]);
}
time = timeSeries[i] + duration - 1;
}
return (total + duration);
}
}