Domain 2MediumCORE

Teemo Attacking

We are given a sorted list of attack times (timeSeries) and a fixed poison duration. We need to calculate the total time Ashe remains poisoned.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

495. Teemo Attacking

Model: qwen3.5:9b
Topics: Array
FAANG asked: 0
Acceptance rate: 56.1%


Problem Breakdown

We are given a sorted list of attack times (timeSeries) and a fixed poison duration. We need to calculate the total time Ashe remains poisoned.

Inputs:

  • timeSeries: A list of integers representing ascending timestamps when Teemo attacks.
  • duration: An integer representing how long each individual attack poisons Ashe.

Outputs:

  • An integer representing the cumulative duration Ashe is in a poisoned state.

Constraints & Edge Cases:

  1. Empty Input: If no attacks occur, total time should be 0.
  2. Overlapping Attacks: A new attack can interrupt an existing poison status. The effective poisoning from that specific interval stops at the start of the next attack if it occurs before the current duration expires.
  3. Non-Overlap: If the gap between attacks is greater than duration, we count full durations for both intervals independently.
  4. Data Types: Inputs are non-negative integers up to 10710^7. Python handles large integers natively, so overflow isn’t a concern here.

Intuition

A brute-force approach might try to simulate every second or minute of time on the timeline (e.g., iterating from min(timeSeries) to max(timeSeries) + duration). However, since values can be up to 10710^7, an iteration over actual seconds would result in Time Complexity proportional to the value range (O(MaxTime)O(\text{MaxTime})), which is too slow.

The key insight is that we don’t need to simulate time; we just need to sum the effective intervals contributed by each attack. For any two consecutive attacks at tit_i and ti+1t_{i+1}, the poison from tit_i would naturally last until ti+durationt_i + \text{duration}. However, if a new attack happens before that (ti+1<ti+durationt_{i+1} < t_i + \text{duration}), we only count up to ti+1t_{i+1}. If there is no overlap (gap ≥\ge duration), we count the full duration.

This suggests a linear scan where for every interval between attacks, we add min⁡(duration,next_attack−current_attack)\min(\text{duration}, \text{next\_attack} - \text{current\_attack}), and finally add the remaining duration of the last attack.

Approach

  1. Handle Empty Case: If timeSeries is empty or has one element (handled naturally by logic, but good to note), return appropriate value. Actually, a single element loop range handles it cleanly if we separate the last iteration.
  2. Iterate Through Intervals: Loop through the array from index 00 up to length - 1.
  3. Calculate Contribution: For each attack at timeSeries[i], calculate the time until the next attack: diff = timeSeries[i+1] - timeSeries[i].
  4. Accumulate Time: Add min⁡(duration,diff)\min(\text{duration}, \text{diff}) to our running total for every interval except the last one.
  5. Final Attack: For the very last attack in the list, there is no subsequent interruption, so we simply add duration directly.
  6. Return Result.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the length of timeSeries. We iterate through the array exactly once with a constant number of operations per element.
  • Space Complexity: O(1)O(1). We only use variables to store the running total and temporary differences; no additional data structures are required.

Solution

def findPoisonedDuration(timeSeries, duration):
    if not timeSeries:
        return 0
    
    total_time = 0
    n = len(timeSeries)
    
    # Iterate through all attacks except the last one to handle overlaps/gaps
    for i in range(n - 1):
        gap = timeSeries[i + 1] - timeSeries[i]
        # Add effective duration: either full poison or until next attack starts
        total_time += min(duration, gap)
    
    # The last attack always contributes its full duration as there is no subsequent interruption
    total_time += duration
    
    return total_time

# Example usage matching problem description
print(findPoisonedDuration([1, 4], 2))   # Output: 4
print(findPoisonedDuration([1, 2], 2))   # Output: 3

Edge Cases Handled

  • Empty Array: The function checks if not timeSeries and returns 0 immediately.
  • Single Attack Element: If N=1N=1, the loop range is empty (range(0)), so it skips to adding duration, which is correct behavior for a single isolated attack.
  • Consecutive Attacks with No Gap (timeSeries[i+1] == timeSeries[i]): The gap becomes 0, min⁡(duration,0)\min(\text{duration}, 0) adds 0, effectively resetting the timer at that exact moment (though problem implies strictly ascending usually; if duplicates exist, logic holds).
  • Large Values: Python handles large integers automatically without overflow issues.