Teemo Attacking - Solution & Explanation

Q: Is Teemo Attacking easy or hard?

Teemo Attacking is categorized as an Easy problem on LeetCode. The challenge is recognizing that overlapping poison effects should only add the extra time between attacks. Once that insight is clear, the implementation becomes a straightforward linear scan.

Q: How to solve Teemo Attacking in O(n)?

Iterate through the timeSeries array and compute the difference between consecutive attack times. Add the minimum of the attack gap and the poison duration to the total. After the loop, add one full duration for the final attack. This single pass approach correctly handles overlapping poison effects.

Q: What is the best approach for Teemo Attacking?

The most efficient approach is an O(n) iterative calculation that processes the attack timestamps sequentially. For each pair of attacks, add min(duration, nextAttack - currentAttack) to the total poison time. Finally add the duration for the last attack. This handles overlapping poison intervals without explicitly merging them.

Q: What data structure is used in Teemo Attacking?

The problem primarily uses an array to store attack timestamps. The solution relies on sequential traversal and arithmetic comparisons rather than complex data structures. Some explanations model the logic as interval processing or simulation.

Q: What is the time complexity of Teemo Attacking?

The optimal solution runs in O(n) time where n is the number of attacks in the timeSeries array. Each timestamp is processed exactly once. Space complexity is O(1) because the algorithm only stores a few counters and does not allocate additional data structures.

Q: Teemo Attacking Python or Java solution approach?

Both Python and Java implementations follow the same logic: iterate through the array and accumulate min(duration, timeSeries[i+1] - timeSeries[i]). After finishing the loop, add duration for the final attack. The algorithm stays O(n) time and O(1) space in both languages.

Q: Is Teemo Attacking asked at Google, Amazon, or Meta?

Teemo Attacking appears frequently in interview preparation sets and has been reported in interviews at companies that test fundamental array and interval reasoning. It focuses on clean iteration logic and understanding overlapping intervals, a common pattern in technical interviews.

EasyArray Simulation13 min readAsked at: Amazon, Google, TCS +2

Practice this problem

Problem Statement

Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly duration seconds. More formally, an attack at second t will mean Ashe is poisoned during the inclusive time interval [t, t + duration - 1]. If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will end duration seconds after the new attack.

You are given a non-decreasing integer array timeSeries, where timeSeries[i] denotes that Teemo attacks Ashe at second timeSeries[i], and an integer duration.

Return the total number of seconds that Ashe is poisoned.

Example 1:

Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: 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
Explanation: 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 <= 10⁴
0 <= timeSeries[i], duration <= 10⁷
timeSeries is sorted in non-decreasing order.

Approach Overview

Problem Overview: You are given an array timeSeries where each value represents the second when Teemo attacks Ashe. Every attack poisons Ashe for duration seconds. If another attack happens before the poison ends, the timer resets. The task is to compute the total time Ashe remains poisoned.

Approach 1: Iterative Calculation of Poison Duration (O(n) time, O(1) space)

This approach scans the attack timeline once and calculates how much poison each attack contributes. For two consecutive attacks at timeSeries[i] and timeSeries[i+1], compute the gap between them. If the gap is smaller than duration, the poison overlaps and only the gap contributes. If the gap is larger, the full duration is added. In practice, you iterate through the array and accumulate min(duration, timeSeries[i+1] - timeSeries[i]) for each pair, then add one final duration for the last attack. This works because overlapping intervals never need to be merged explicitly; the difference between timestamps already tells you the extra poisoned time. The approach is simple, linear, and uses constant memory. It relies only on sequential traversal of the array and direct arithmetic comparisons.

Approach 2: Dynamic Programming with Overlapping Intervals (O(n) time, O(1) space)

This method treats the problem as a sequence of overlapping intervals. Each attack creates an interval [timeSeries[i], timeSeries[i] + duration). The DP idea tracks the end of the previous poison interval and decides whether the current attack overlaps with it. If the new attack occurs after the previous poison ends, add the full duration. If it occurs before the previous poison expires, only add the extension beyond the current end. The state you maintain is simply the end time of the active poison window. During iteration, update the end boundary and accumulate the additional poisoned seconds. Conceptually this resembles interval merging and fits naturally into problems involving simulation or dynamic programming over time-based states.

Recommended for interviews: The iterative calculation approach is what most interviewers expect. It demonstrates that you recognize the overlapping interval pattern and reduce it to a simple difference calculation. The DP-style interval tracking also works and helps if you think in terms of interval merging, but the direct iteration with min(duration, gap) is the cleanest and most commonly discussed solution.

Approach 1: Iterative Calculation of Poison Duration

This approach involves iteratively calculating the poison effect duration from the attack times given in timeSeries. The idea is to maintain a running total of poison duration impacts caused by each attack, making adjustments for overlaps where a new attack resets the poison timer.

The solution iterates over the array, and for each attack time, it calculates the increment to the total poison duration. If the next attack occurs after the current poison effect ends, it simply adds the full duration. Otherwise, it adds only the period from the current attack time to the next one (since next attack resets the poison).

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the number of attack times in timeSeries.
Space Complexity: O(1), as we only use a limited amount of extra space.

Try this approach in the editor →

Approach 2: Dynamic Programming with Overlapping Intervals

In this approach, we utilize a dynamic programming technique to handle overlapping intervals. The essence here is to consider the overlap between poison effects and adjust the ending intervals of these periods dynamically.

This C solution manages the end of the current poison effect period, adjusting it dynamically with each attack. It checks for overlapped periods and updates the total duration based on effective poisoning time.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) since we iterate through timeSeries just once.
Space Complexity: O(1) due to using minimal additional memory.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go TypeScript C#

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Iterative Calculation of Poison Duration	Time Complexity: O(n), where n is the number of attack times in `timeSeries`. Space Complexity: O(1), as we only use a limited amount of extra space.
Dynamic Programming with Overlapping Intervals	Time Complexity: O(n) since we iterate through `timeSeries` just once. Space Complexity: O(1) due to using minimal additional memory.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Iterative Calculation of Poison Duration	O(n)	O(1)	Best general solution when attacks are processed sequentially
Dynamic Programming with Overlapping Intervals	O(n)	O(1)	Useful when thinking in terms of interval extension or state tracking

Video Solution

teemo attacking | teemo attacking leetcode | leetcode 495 | java python3 c++ • Naresh Gupta • 3,564 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Teemo Attacking easy or hard?

Teemo Attacking is categorized as an Easy problem on LeetCode. The challenge is recognizing that overlapping poison effects should only add the extra time between attacks. Once that insight is clear, the implementation becomes a straightforward linear scan.

How to solve Teemo Attacking in O(n)?

Iterate through the timeSeries array and compute the difference between consecutive attack times. Add the minimum of the attack gap and the poison duration to the total. After the loop, add one full duration for the final attack. This single pass approach correctly handles overlapping poison effects.

What is the best approach for Teemo Attacking?

The most efficient approach is an O(n) iterative calculation that processes the attack timestamps sequentially. For each pair of attacks, add min(duration, nextAttack - currentAttack) to the total poison time. Finally add the duration for the last attack. This handles overlapping poison intervals without explicitly merging them.

What data structure is used in Teemo Attacking?

The problem primarily uses an array to store attack timestamps. The solution relies on sequential traversal and arithmetic comparisons rather than complex data structures. Some explanations model the logic as interval processing or simulation.

What is the time complexity of Teemo Attacking?

The optimal solution runs in O(n) time where n is the number of attacks in the timeSeries array. Each timestamp is processed exactly once. Space complexity is O(1) because the algorithm only stores a few counters and does not allocate additional data structures.

Teemo Attacking Python or Java solution approach?

Both Python and Java implementations follow the same logic: iterate through the array and accumulate min(duration, timeSeries[i+1] - timeSeries[i]). After finishing the loop, add duration for the final attack. The algorithm stays O(n) time and O(1) space in both languages.

Is Teemo Attacking asked at Google, Amazon, or Meta?

Teemo Attacking appears frequently in interview preparation sets and has been reported in interviews at companies that test fundamental array and interval reasoning. It focuses on clean iteration logic and understanding overlapping intervals, a common pattern in technical interviews.

Ready to solve this problem?

Practice Teemo Attacking with our built-in code editor and test cases.

Practice on FleetCode

Can Place Flowers

Dota2 Senate

Problem Info

DifficultyEasy

Acceptance57.6%

Approaches3

Reading time13 min

Asked at

Amazon Google TCS Jane Street Riot Games

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Iterative Calculation of Poison Duration

Code

Complexity

Approach 2: Dynamic Programming with Overlapping Intervals

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents