Teemo Attacking

Problem Description

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.

Key Insights

• Each attack at time t affects Ashe for duration seconds.
• If a new attack occurs within the duration of the previous attack, it resets the poison timer.
• We need to account for overlapping intervals of poison effects.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can iterate through the timeSeries array and calculate the total poisoned time. We maintain a variable to keep track of the end time of the current poison effect. For each attack:

1. If the attack time is greater than the end time of the previous poison effect, we can simply add the full duration to the total.
2. If the attack time is within the current poison effect (i.e., it overlaps), we calculate the additional time that Ashe gets poisoned by considering the remaining time from the end of the previous poison effect.

This approach ensures that we only traverse the timeSeries array once, resulting in a time complexity of O(n). We use constant space for our variables.

Code Solutions