Teemo Attacking: Merging Overlapping Intervals

May 19, 20264 min read

leetcodeproblemeasyarrays

LeetCode 495, Teemo Attacking, is a clean introduction to interval overlap logic. Teemo attacks Ashe at specific times given in a sorted array timeSeries. Each attack applies poison for duration seconds. If Teemo attacks again before the poison wears off, the timer resets - it does not stack. You need to find the total number of seconds Ashe is poisoned.

This problem is simpler than classic interval merging because the input is already sorted and you only need the total length, not the merged intervals themselves. But the core idea is the same: when intervals overlap, you cannot just add up all the durations.

Example 1: timeSeries = [1, 4], duration = 2 (no overlap)

Example 2: timeSeries = [1, 2], duration = 2 (overlap)

When attacks overlap, the second attack resets the poison timer. The actual poisoned time is min(duration, gap) for each pair, plus duration for the last attack.

Look at the two examples above. When attacks are far apart, each one contributes the full duration. When attacks are close together, the second attack cuts the first one short. The poison from the first attack only lasts until the next attack arrives, at which point the timer resets.

The key insight

For any two consecutive attacks at times timeSeries[i] and timeSeries[i+1], the gap between them is timeSeries[i+1] - timeSeries[i]. If that gap is at least duration, the first attack contributes the full duration of poison. If the gap is smaller, the first attack only contributes gap seconds before getting cut short by the next attack.

In other words, for each attack except the last, its contribution is min(duration, timeSeries[i+1] - timeSeries[i]). The last attack always contributes the full duration because nothing comes after it to reset the timer.

Practice this problem with spaced repetition

The solution

def findPoisonedDuration(timeSeries, duration):
    if not timeSeries:
        return 0

    total = 0
    for i in range(len(timeSeries) - 1):
        total += min(duration, timeSeries[i + 1] - timeSeries[i])

    total += duration
    return total

The algorithm walks through each consecutive pair of attacks and adds the effective poisoned time. For each pair, min(duration, gap) handles both cases: if the gap is large enough, you add the full duration; if the attacks overlap, you add only the gap. After the loop, you add duration for the final attack.

Let's trace through an example with timeSeries = [1, 2, 6, 7] and duration = 3.

Step 1: Process attack at t=1. Next attack at t=2, gap = 1.

total_poisoned = 1

gap (1) < duration (3), so only 1 second of poison counts. Add min(3, 1) = 1.

Step 2: Process attack at t=2. Next attack at t=6, gap = 4.

total_poisoned = 4

gap (4) >= duration (3), so the full duration counts. Add min(3, 4) = 3.

Step 3: Process attack at t=6. Next attack at t=7, gap = 1.

total_poisoned = 5

gap (1) < duration (3), so only 1 second counts. Add min(3, 1) = 1.

Step 4: Process last attack at t=7. No next attack.

total_poisoned = 8

Last attack always contributes the full duration. Add 3. Total = 8 seconds.

The overlapping attacks at t=1 and t=2 only contribute 1 second instead of 3, because the second attack arrives after just 1 second. Same for t=6 and t=7. But the attack at t=2 contributes the full 3 seconds because the next attack at t=6 is 4 seconds away, which is more than duration. The total is 1 + 3 + 1 + 3 = 8 seconds.

Build your pattern library with CodeBricks

Complexity analysis

Approach	Time	Space
Linear scan	O(n)	O(1)

You scan the array once and use a constant amount of extra space. The input is already sorted, so no sorting step is needed. This is optimal - you need to look at every attack time at least once.

The building blocks

This problem is a simplified version of the interval merging pattern. In Merge Intervals, you need to sort the input and produce the actual merged intervals. Here, the input is pre-sorted and you only need the total length.

The core technique is the same: compare consecutive intervals and decide whether they overlap. If the gap between them is smaller than the interval length, they overlap and you only count the gap. If the gap is large enough, they are separate and you count the full interval.

This "min of gap and duration" pattern shows up whenever you need to compute the total coverage of potentially overlapping intervals on a number line. Once you recognize it, the implementation is a simple loop.

Edge cases to watch for

Empty array. If timeSeries is empty, return 0. There are no attacks, so no poison.

Single attack. If there is only one attack, the answer is simply duration. The loop body never executes, and you just add duration at the end.

All attacks overlap. Something like timeSeries = [1, 2, 3, 4] with duration = 5. Every gap is 1, so each attack except the last contributes just 1 second. Total = 3 * 1 + 5 = 8.

No attacks overlap. For example timeSeries = [1, 10, 20] with duration = 3. Every gap exceeds the duration, so each attack contributes the full 3 seconds. Total = 3 * 3 = 9.

From understanding to recall

This is one of those problems where the solution is short but the reasoning matters. You need to internalize why min(duration, gap) is the right formula and why the last attack always gets the full duration. If you just memorize the code without understanding the overlap logic, you will struggle when the same pattern appears in harder problems like Merge Intervals or Non-overlapping Intervals.

Practice reproducing the solution from scratch. Draw the timeline, label the gaps, and convince yourself that min(duration, gap) handles both overlapping and non-overlapping cases. Once that clicks, this problem becomes a building block you can reuse.

Merge Intervals - The full interval merging pattern with sorting
Non-overlapping Intervals - Greedy interval scheduling to minimize removals
Insert Interval - Inserting and merging into a sorted interval list

Try CodeBricks free