Teemo Attacking

Teemo Attacking

What is this problem about?

The Teemo Attacking interview question is a straightforward simulation problem. You are given an array of time points where an attack occurs and a duration d for a "poisoned" condition. When an attack happens at time t, the enemy is poisoned for the interval [t, t + d - 1]. If another attack happens while the enemy is already poisoned, the timer resets. Your goal is to find the total amount of time the enemy is poisoned.

Why is this asked in interviews?

Companies like Riot Games and Jane Street ask this "Easy" level question to test basic array iteration and interval management. It evaluates whether you can handle overlapping intervals efficiently in a single pass. It’s a great way to check a candidate's attention to detail—specifically, ensuring that the duration of an attack is not double-counted when a second attack happens shortly after the first.

Algorithmic pattern used

The primary pattern is the Single-Pass Array Simulation or Interval Merging pattern.

1. Iterate through the timeSeries array from the first element to the second-to-last element.
2. For each attack at timeSeries[i], calculate the gap until the next attack: gap = timeSeries[i+1] - timeSeries[i].
3. The poisoned time contributed by this attack is the minimum of the duration d and the gap.
4. After the loop, add the full duration d for the very last attack (since it can't be interrupted).

Example explanation

Attacks at [1, 4], duration 3.

• Attack 1 at time 1: Next attack is at 4. Gap is 4 - 1 = 3. Poison lasts from 1 to 3. Contributes min(3, 3) = 3.
• Attack 2 at time 4: Last attack. Contributes full duration 3. Poison lasts from 4 to 6.
• Total time = 3 + 3 = 6. If attacks were at [1, 2] and duration was 3:
• Attack 1 at time 1: Next is 2. Gap is 1. Contributes min(1, 3) = 1.
• Attack 2 at time 2: Contributes 3.
• Total time = 1 + 3 = 4.

Common mistakes candidates make

A common error is trying to track the end time of the poison and the start time of the next attack with complex logic, which can lead to off-by-one errors. Another mistake is forgetting to add the duration for the final attack in the array. Using a nested loop to check every second (O(total_time)) is also a poor approach if the time points are very large.

Interview preparation tip

To prepare for the Teemo Attacking coding problem, practice thinking about the "contribution" of each event in an array. This is a common theme in the Array interview pattern. Understanding how to handle overlapping intervals is a fundamental skill for more complex scheduling and geometry problems.