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:
- Empty Input: If no attacks occur, total time should be 0.
- 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.
- Non-Overlap: If the gap between attacks is greater than
duration, we count full durations for both intervals independently. - Data Types: Inputs are non-negative integers up to . 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 , an iteration over actual seconds would result in Time Complexity proportional to the value range (), 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 and , the poison from would naturally last until . However, if a new attack happens before that (), we only count up to . If there is no overlap (gap duration), we count the full duration.
This suggests a linear scan where for every interval between attacks, we add , and finally add the remaining duration of the last attack.
Approach
- Handle Empty Case: If
timeSeriesis 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. - Iterate Through Intervals: Loop through the array from index up to length - 1.
- Calculate Contribution: For each attack at
timeSeries[i], calculate the time until the next attack:diff = timeSeries[i+1] - timeSeries[i]. - Accumulate Time: Add to our running total for every interval except the last one.
- Final Attack: For the very last attack in the list, there is no subsequent interruption, so we simply add
durationdirectly. - Return Result.
Complexity Analysis
- Time Complexity: where is the length of
timeSeries. We iterate through the array exactly once with a constant number of operations per element. - Space Complexity: . 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 timeSeriesand returns 0 immediately. - Single Attack Element: If , 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, 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.