Problem
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.
Approach
Today’s randomly picked question. I have to say, the problem description is the worst of what I have encountred, for obvious reasons. And yes, I don’t like LOL.
My first thought is to use a set to store all of the timeSeries and setup an integer to keep track of the debuff time. Therefore, when iterating through the time from (0 or from timeSeries[0]), we could check if there is another poison casted at the time and reset the debuff time. This algorithm some how passes all the test without TLE (I thought it will). The following is the implementation of the solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int debuffTotal = 0;
int curDuration = 0;
std::unordered_set<int> timeSet(timeSeries.begin(), timeSeries.end());
for (int time = 0; time <= timeSeries.back()+duration; time++) {
if (timeSet.count(time)) {
curDuration = duration;
}
if (curDuration-- > 0) debuffTotal++;
}
return debuffTotal;
}
};
However there is a much more simpler solution. Simply iterate through timeSeries, if the next element in the series compared to the current element is less then duration, then the whole segment ( timeSeries[i+1] - timeSeries[i]) will be under poison’s effect.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int findPoisonedDuration(std::vector<int>& timeSeries, int duration) {
int debuffTotal = 0;
if (timeSeries.size() == 0) return 0;
for (int i = 0; i < timeSeries.size() - 1; i++) {
debuffTotal += std::min(timeSeries[i + 1] - timeSeries[i], duration);
}
return debuffTotal + duration;
}
};