#495

Easy

LeetCode Problem Workspace

Teemo Attacking

Compute the total poisoned time Ashe experiences from Teemo's attacks using an array-based simulation approach efficiently.

array simulation

Problem Statement

Teemo attacks Ashe at various seconds, poisoning her for a fixed duration per attack. If a new attack occurs before the previous poison expires, the timer resets, and overlapping time should not be double-counted.

Given a non-decreasing array timeSeries representing the seconds when Teemo attacks and an integer duration, compute the total number of seconds Ashe is poisoned throughout all attacks.

Examples

Example 1

Input: timeSeries = [1,4], duration = 2

Output: 4

Teemo's attacks on Ashe go as follows:

At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5. Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

Example 2

Input: timeSeries = [1,2], duration = 2

Output: 3

Teemo's attacks on Ashe go as follows:

At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
At second 2 however, Teemo attacks again and resets the poison timer. Ashe is poisoned for seconds 2 and 3. Ashe is poisoned for seconds 1, 2, and 3, which is 3 seconds in total.

Constraints

1 <= timeSeries.length <= 104
0 <= timeSeries[i], duration <= 107
timeSeries is sorted in non-decreasing order.

Solution Approach

Iterate and Compare Attack Times

Traverse the timeSeries array from start to end. For each attack, calculate the end of its poison duration. If the next attack occurs after the current poison ends, add the full duration; otherwise, add only the non-overlapping interval.

Accumulate Poisoned Duration

Maintain a running total of poisoned seconds. At each step, compare the current attack's start time with the previous poison's end time to determine overlap. Add either the full duration or the difference to the total accordingly.

Return Total Poison Time

After processing all attacks, the accumulated total represents the exact number of seconds Ashe is poisoned. This approach ensures correct counting for overlapping attacks and leverages the array's sorted property for linear traversal.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N)
Space	\mathcal{O}(1)

Time complexity is O(N) since each attack is processed once. Space complexity is O(1) as only a few variables track the total poisoned time and previous poison end.

What Interviewers Usually Probe

Focus on handling overlapping poison durations correctly.
Check if candidates use linear iteration instead of nested loops.
See if the candidate accounts for edge cases when attacks occur back-to-back.

Common Pitfalls or Variants

Common pitfalls

Double-counting seconds when poison durations overlap.
Ignoring the inclusive nature of poison intervals.
Using extra space unnecessarily instead of O(1) accumulation.

Follow-up variants

Allow unsorted timeSeries array and require sorting before processing.
Change poison duration dynamically per attack, requiring interval comparison.
Compute maximum continuous poisoned interval instead of total poisoned seconds.

FAQ

What is the main idea behind Teemo Attacking problem?

The problem uses array simulation to calculate total poisoned time while properly handling overlapping attacks.

How do I handle overlapping poison intervals efficiently?

Compare each attack's start time with the previous poison end time and add only the non-overlapping portion.

Can timeSeries have zero length?

Constraints guarantee at least one attack, so timeSeries always has length >= 1.

Why is linear iteration sufficient for this problem?

Because timeSeries is sorted, each attack can be processed once without revisiting previous attacks, achieving O(N) time.

Does GhostInterview simulate Array plus Simulation patterns automatically?

Yes, it models poison intervals over the array to calculate exact totals while accounting for overlaps and resets.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        ans = duration
        for a, b in pairwise(timeSeries):
            ans += min(duration, b - a)
        return ans

Continue Practicing

#498 diagonal traverse #566 reshape the matrix #682 baseball game