Approach 1: One pass
The problem is an example of merge interval questions which are now quite popular in Google.
Here one deals with a sorted input, and the problem could be solved in one pass
with a constant space.
The idea is straightforward: consider only the interval between two attacks.
Ashe spends in a poisoned condition the whole time interval
if this interval is shorter than the poisoning time duration
Initiate total time in poisoned condition
total = 0.
timeSerieslist. At each step add to the total time the minimum between interval length and the poisoning time duration
total + durationto take the last attack into account.
Time complexity : , where N is the length of the input list, since we iterate the entire list.
Space complexity : , it's a constant space solution.