Teemo Attacking solution and explanation
TCS
Google
9 more videos on this problem
teemo attacking | teemo attacking leetcode | leetcode 495 | java python3 c++Naresh Gupta · 6:40 · 3K views
495. Teemo Attacking | LEETCODE EASYcode Explainer · 4:44 · 2K views
Teemo Attacking | Leet code 495 | Theory explained + Python codeSai Anish Malla · 9:35 · 1K views
Leetcode - Teemo Attacking (Python)Timothy H Chang · 5:45 · 1K views
Leetcode 495 Teemo Attacking videoEasyLeetcode · 5:07 · 1K views
Teemo Attacking | LeetCode 495 | September LeetCode Challenge | Day 26Learn Code Repeat · 11:14 · 558 views
495. Teemo Attacking || LEETCODE SOLUTION || IN C++ || DATA STRUCTURE AND ALGORITHMAbhishweta Gupta · 2:08 · 527 views
495. Teemo Attacking (Leetcode Medium)Programming Live with Larry · 15:00 · 354 views
Teemo Attacking Leetcode - 495 C++Code Crash · 6:14 · 315 views
Teemo Attacking | September Leetcode Challenge | Leetcode 495 | Day 26Ayushi Rawat · 6:28 · 289 views
The problem
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 <= 1040 <= timeSeries[i], duration <= 107timeSeriesis 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.
def findPoisonedDuration(timeSeries, duration):
totalDuration = 0
for i in range(len(timeSeries)):
if i == len(timeSeries) - 1 or timeSeries[i + 1] >= timeSeries[i] + duration:
totalDuration += duration
else:
totalDuration += timeSeries[i + 1] - timeSeries[i]
return totalDuration
# Example usage
print(findPoisonedDuration([1, 4], 2))public class TeemoAttacking {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int totalDuration = 0;
for (int i = 0; i < timeSeries.length; i++) {
if (i == timeSeries.length - 1 || timeSeries[i + 1] >= timeSeries[i] + duration) {
totalDuration += duration;
} else {
totalDuration += timeSeries[i + 1] - timeSeries[i];
}
}
return totalDuration;
}
public static void main(String[] args) {
TeemoAttacking ta = new TeemoAttacking();
int[] timeSeries = {1, 4};
int duration = 2;
System.out.println(ta.findPoisonedDuration(timeSeries, duration));
}
}#include <vector>
using namespace std;
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int totalDuration = 0;
for (int i = 0; i < timeSeries.size(); i++) {
if (i == timeSeries.size() - 1 || timeSeries[i + 1] >= timeSeries[i] + duration) {
totalDuration += duration;
} else {
totalDuration += timeSeries[i + 1] - timeSeries[i];
}
}
return totalDuration;
}
#include <iostream>
int main() {
vector<int> timeSeries = {1, 4};
int duration = 2;
cout << findPoisonedDuration(timeSeries, duration) << endl;
return 0;
}function findPoisonedDuration(timeSeries, duration) {
let totalDuration = 0;
for (let i = 0; i < timeSeries.length; i++) {
if (i === timeSeries.length - 1 || timeSeries[i + 1] >= timeSeries[i] + duration) {
totalDuration += duration;
} else {
totalDuration += timeSeries[i + 1] - timeSeries[i];
}
}
return totalDuration;
}
console.log(findPoisonedDuration([1, 4], 2));#include <stdio.h>
int findPoisonedDuration(int* timeSeries, int timeSeriesSize, int duration) {
int totalDuration = 0;
for (int i = 0; i < timeSeriesSize; i++) {
if (i == timeSeriesSize - 1 || timeSeries[i + 1] >= timeSeries[i] + duration) {
totalDuration += duration;
} else {
totalDuration += timeSeries[i + 1] - timeSeries[i];
}
}
return totalDuration;
}
int main() {
int timeSeries[] = {1, 4};
int duration = 2;
int size = sizeof(timeSeries) / sizeof(timeSeries[0]);
printf("%d\n", findPoisonedDuration(timeSeries, size, duration));
return 0;
}using System;
public class TeemoAttacking {
public int FindPoisonedDuration(int[] timeSeries, int duration) {
int totalDuration = 0;
for (int i = 0; i < timeSeries.Length; i++) {
if (i == timeSeries.Length - 1 || timeSeries[i + 1] >= timeSeries[i] + duration) {
totalDuration += duration;
} else {
totalDuration += timeSeries[i + 1] - timeSeries[i];
}
}
return totalDuration;
}
public static void Main(string[] args) {
TeemoAttacking ta = new TeemoAttacking();
int[] timeSeries = {1, 4};
int duration = 2;
Console.WriteLine(ta.FindPoisonedDuration(timeSeries, duration));
}
}The Python implementation loops through the attack times while checking conditions for poison duration accumulation. Depending on whether the poison was reset or not, different amounts of time are added to the total on each iteration.
Time Complexity: O(n), given n is the number of attacks.
Space Complexity: O(1), as operations are performed in-place without extra memory.
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.
def findPoisonedDuration(timeSeries, duration):
if not timeSeries: return 0
totalDuration = 0
end = timeSeries[0] + duration
for i in range(1, len(timeSeries)):
if timeSeries[i] < end:
totalDuration += timeSeries[i] - timeSeries[i-1]
else:
totalDuration += duration
end = timeSeries[i] + duration
totalDuration += duration
return totalDuration
# Example usage
print(findPoisonedDuration([1, 4], 2))public class TeemoAttacking {
public int findPoisonedDuration(int[] timeSeries, int duration) {
if (timeSeries.length == 0) return 0;
int totalDuration = 0;
int end = timeSeries[0] + duration;
for (int i = 1; i < timeSeries.length; ++i) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i - 1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration;
return totalDuration;
}
public static void main(String[] args) {
TeemoAttacking ta = new TeemoAttacking();
int[] timeSeries = {1, 4};
int duration = 2;
System.out.println(ta.findPoisonedDuration(timeSeries, duration));
}
}#include <vector>
using namespace std;
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
if (timeSeries.empty()) return 0;
int totalDuration = 0;
int end = timeSeries[0] + duration;
for (int i = 1; i < timeSeries.size(); ++i) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i - 1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration;
return totalDuration;
}
#include <iostream>
int main() {
vector<int> timeSeries = {1, 4};
int duration = 2;
cout << findPoisonedDuration(timeSeries, duration) << endl;
return 0;
}function findPoisonedDuration(timeSeries, duration) {
if (timeSeries.length === 0) return 0;
let totalDuration = 0;
let end = timeSeries[0] + duration;
for (let i = 1; i < timeSeries.length; i++) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i-1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration;
return totalDuration;
}
console.log(findPoisonedDuration([1, 4], 2));#include <stdio.h>
int findPoisonedDuration(int* timeSeries, int timeSeriesSize, int duration) {
if (timeSeriesSize == 0) return 0;
int totalDuration = 0;
int end = timeSeries[0] + duration;
for (int i = 1; i < timeSeriesSize; ++i) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i - 1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration; // account for the last attack
return totalDuration;
}
int main() {
int timeSeries[] = {1, 4};
int duration = 2;
printf("%d\n", findPoisonedDuration(timeSeries, 2, duration));
return 0;
}using System;
public class TeemoAttacking {
public int FindPoisonedDuration(int[] timeSeries, int duration) {
if (timeSeries.Length == 0) return 0;
int totalDuration = 0;
int end = timeSeries[0] + duration;
for (int i = 1; i < timeSeries.Length; ++i) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i - 1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration;
return totalDuration;
}
public static void Main(string[] args) {
TeemoAttacking ta = new TeemoAttacking();
int[] timeSeries = {1, 4};
int duration = 2;
Console.WriteLine(ta.FindPoisonedDuration(timeSeries, duration));
}
}The Python code handles poisoning implementation using dynamic calculation of the current poison effect's end time. Adjustments are made for overlaps, and the final duration is computed efficiently.
Time Complexity: O(n), iterating over the attacks only once.
Space Complexity: O(1), given only a constant amount of memory is used.
Approach 3: Default Approach
function findPoisonedDuration(timeSeries: number[], duration: number): number {
const n = timeSeries.length;
let ans = duration;
for (let i = 1; i < n; ++i) {
ans += Math.min(duration, timeSeries[i] - timeSeries[i - 1]);
}
return ans;
}func findPoisonedDuration(timeSeries []int, duration int) (ans int) {
ans = duration
for i, x := range timeSeries[1:] {
ans += min(duration, x-timeSeries[i])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Calculation of Poison Duration | Time Complexity: O(n), given n is the number of attacks. |
| Dynamic Programming with Overlapping Intervals | Time Complexity: O(n), iterating over the attacks only once. |
| Default Approach | – |
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 |
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.