Problem Description

This problem is about calculating the total duration of a poison effect on a character named Ashe when attacked by Teemo.

The key mechanics are:

• Each attack from Teemo poisons Ashe for exactly duration seconds
• When an attack happens at time t, Ashe is poisoned during the interval [t, t + duration - 1] (inclusive)
• If a new attack occurs while Ashe is still poisoned, the poison timer resets and starts counting duration seconds from the new attack time
• The poison effects don't stack - they only reset

You're given:

• timeSeries: A non-decreasing array where each element represents the time (in seconds) when Teemo attacks
• duration: The number of seconds each poison effect lasts

The goal is to calculate the total number of seconds that Ashe remains poisoned throughout all attacks.

For example, if timeSeries = [1, 4] and duration = 3:

• First attack at t=1 poisons Ashe during [1, 3]
• Second attack at t=4 poisons Ashe during [4, 6]
• Total poisoned time = 3 + 3 = 6 seconds

But if timeSeries = [1, 2] and duration = 3:

• First attack at t=1 would poison during [1, 3]
• Second attack at t=2 resets the timer, poisoning during [2, 4]
• The overlap means total poisoned time = 4 seconds (not 6)

The solution iterates through consecutive attack pairs and adds either the full duration (if attacks are far apart) or the actual gap between attacks (if they're close enough to overlap).

Intuition

The key insight is to think about what happens between consecutive attacks. When we have two attacks, there are only two possible scenarios:

1. Attacks are far apart: If the time between two attacks is greater than or equal to duration, the poison from the first attack completely expires before the second attack. In this case, the first attack contributes exactly duration seconds to the total.

2. Attacks overlap: If the second attack happens while the poison from the first attack is still active (gap < duration), the poison timer resets. Here, the first attack only contributes the gap time between the two attacks, not the full duration.

This leads us to a simple pattern: for each pair of consecutive attacks at times a and b, the poison duration contributed by attack a is min(duration, b - a). We take the minimum because:

• If b - a >= duration, the poison runs its full course, contributing duration seconds
• If b - a < duration, the poison gets cut short by the next attack, contributing only b - a seconds

The last attack in the series always contributes the full duration since there's no subsequent attack to interrupt it.

By iterating through all consecutive pairs and summing up these contributions, plus adding the full duration for the final attack, we get the total poisoned time. This approach avoids the complexity of tracking overlapping intervals explicitly - we simply calculate the effective duration for each attack based on when the next one occurs.

Solution Approach

The implementation uses a simple iteration through consecutive pairs of attack times to calculate the total poison duration.

Algorithm Steps:

1. Initialize the answer: Start with ans = duration to account for the last attack, which always contributes the full duration seconds since no subsequent attack can interrupt it.

2. Iterate through consecutive pairs: Use the pairwise function to get consecutive pairs (a, b) from the timeSeries array. This gives us each attack time paired with the next attack time.

3. Calculate contribution for each attack: For each pair (a, b):

   • Calculate the time gap between attacks: b - a
   • The actual poison duration from attack a is min(duration, b - a)
   • Add this value to the running total

4. Return the total: The sum represents the total seconds Ashe is poisoned.

Implementation Details:

ans = duration  # Account for the last attack
for a, b in pairwise(timeSeries):
    ans += min(duration, b - a)
return ans

The pairwise function creates pairs like: [t1, t2, t3] → [(t1, t2), (t2, t3)]

Time Complexity: O(n) where n is the length of timeSeries, as we iterate through the array once.

Space Complexity: O(1) as we only use a constant amount of extra space for the running total.

This approach elegantly handles all edge cases:

• Single attack: Only the initial ans = duration is counted
• Multiple attacks with no overlap: Each contributes full duration
• Overlapping attacks: Each contributes only the gap to the next attack

Example Walkthrough

Let's walk through the solution with timeSeries = [1, 2, 5, 8] and duration = 3.

Step 1: Initialize

• Start with ans = 3 (accounting for the last attack at t=8, which will poison for the full duration [8, 10])

Step 2: Process consecutive pairs

First pair (1, 2):

• Gap between attacks: 2 - 1 = 1 second
• Since gap (1) < duration (3), the poison from t=1 gets interrupted
• Contribution: min(3, 1) = 1 second
• Running total: ans = 3 + 1 = 4

Second pair (2, 5):

• Gap between attacks: 5 - 2 = 3 seconds
• Since gap (3) = duration (3), the poison from t=2 runs its full course
• Contribution: min(3, 3) = 3 seconds
• Running total: ans = 4 + 3 = 7

Third pair (5, 8):

• Gap between attacks: 8 - 5 = 3 seconds
• Since gap (3) = duration (3), the poison from t=5 runs its full course
• Contribution: min(3, 3) = 3 seconds
• Running total: ans = 7 + 3 = 10

Step 3: Return result

• Total poisoned time = 10 seconds

Verification:

• Attack at t=1: poisoned during [1, 2) (interrupted by next attack)
• Attack at t=2: poisoned during [2, 4] (full duration)
• Attack at t=5: poisoned during [5, 7] (full duration)
• Attack at t=8: poisoned during [8, 10] (full duration)
• Total intervals: [1, 2) + [2, 4] + [5, 7] + [8, 10] = 1 + 3 + 3 + 3 = 10 seconds ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the timeSeries array. The pairwise function iterates through the array once, creating pairs of consecutive elements. For each pair, we perform a constant-time operation (min(duration, b - a)), resulting in n-1 iterations. Therefore, the overall time complexity is linear.

Space Complexity: O(1) constant extra space. The pairwise function in Python creates an iterator that yields pairs on-the-fly without storing all pairs in memory. We only use a single variable ans to accumulate the result, and the loop variables a and b which take constant space regardless of input size.

Common Pitfalls

1. Forgetting to Handle Empty Input

A common mistake is not checking if timeSeries is empty before processing. Accessing elements of an empty array will cause an error.

Incorrect approach:

def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
    total = duration  # This assumes there's at least one attack
    for i in range(len(timeSeries) - 1):  # Will skip if array has 0 or 1 element
        total += min(duration, timeSeries[i + 1] - timeSeries[i])
    return total

Issue: Returns duration even when there are no attacks (empty array).

Solution: Add an explicit check for empty input:

if not timeSeries:
    return 0

2. Double-Counting Poison Duration

Some might try to calculate the poison duration for each attack independently and then try to remove overlaps, leading to complex logic and potential errors.

Incorrect approach:

def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
    total = len(timeSeries) * duration  # Assume all attacks contribute full duration
    # Then try to subtract overlaps - this gets complicated and error-prone
    for i in range(len(timeSeries) - 1):
        if timeSeries[i + 1] - timeSeries[i] < duration:
            overlap = duration - (timeSeries[i + 1] - timeSeries[i])
            total -= overlap
    return total

Issue: This approach is more complex and harder to verify correctness.

Solution: Calculate the actual contribution of each attack directly by taking the minimum of the full duration and the gap to the next attack.

3. Off-by-One Errors with Inclusive Intervals

The problem states that an attack at time t poisons during [t, t + duration - 1]. Some might incorrectly calculate this as [t, t + duration], leading to wrong overlap calculations.

Incorrect approach:

def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
    total = 0
    for i in range(len(timeSeries) - 1):
        # Wrong: thinking poison ends at t + duration instead of t + duration - 1
        if timeSeries[i] + duration <= timeSeries[i + 1]:  # Should be < not <=
            total += duration
        else:
            total += timeSeries[i + 1] - timeSeries[i]
    total += duration  # Last attack
    return total

Issue: The condition for non-overlapping intervals is incorrect.

Solution: Remember that the poison effect lasts from [t, t + duration - 1], so two attacks don't overlap if the next attack happens at time t + duration or later. Using min(duration, next_time - current_time) handles this correctly without explicit condition checking.

4. Not Accounting for the Last Attack

It's easy to forget that the last attack always contributes its full duration since there's no subsequent attack to interrupt it.

Incorrect approach:

def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
    total = 0
    for i in range(len(timeSeries) - 1):
        total += min(duration, timeSeries[i + 1] - timeSeries[i])
    return total  # Forgot to add duration for the last attack!

Issue: The loop only processes pairs of attacks, missing the contribution from the final attack.

Solution: Initialize the total with duration to account for the last attack, or add it after the loop completes.