Solution


Approach 1: One pass

Intuition

The problem is an example of merge interval questions which are now quite popular in Google.

Typically such problems could be solved in a linear time in the case of sorted input, like here, and in time otherwise, here is an example.

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 duration, and duration otherwise.

Algorithm

  • Initiate total time in poisoned condition total = 0.

  • Iterate over timeSeries list. At each step add to the total time the minimum between interval length and the poisoning time duration duration.

  • Return total + duration to take the last attack into account.

Implementation

pic

Complexity Analysis

  • 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.

Analysis written by @liaison and @andvary