Easy

Quiz

#495 Teemo Attacking

APPROACH

In a game, Teemo attacks Ashe and each attack poisons her for exactly duration seconds. An attack at second t poisons Ashe during the inclusive interval [t, t + duration - 1]. A new attack before the current poison expires resets the duration from the new attack time onward.

You are given a non-decreasing integer array timeSeries of attack timestamps 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.

1 of 4

1:00

What is the optimal approach for this problem?