Leetcode – Teemo Attacking Solution in Python

Teemo Attacking is a widely-known algorithm problem and can be found on Leetcode. This problem is excellent for understanding array traversal and simple mathematical calculations. In this extensive article, we will explore the problem statement, investigate different approaches to solve this problem in Python, and analyze their complexities.

Problem Statement:

In League of Legends, Teemo is a character that attacks his enemies by planting poison on them. For each attack, the enemy is poisoned for a certain duration of time. We are given an array timeSeries, which represents the time in seconds at which Teemo makes an attack, and an integer duration, which represents the duration in seconds that each attack poisons the enemy. We are required to find the total time in seconds that the enemy is in a poisoned condition.

Example:

Input: timeSeries = [1, 4], duration = 2
Output: 4
Explanation: Teemo's attacks at time 1 and 4 will poison the enemy for 2 seconds. However, at time 4, the poison will refresh, thus the total time the enemy is poisoned is 1 to 3 and 4 to 5, which is 4 seconds in total.

Basic Approach:

A naive approach is to simulate the poisoning process by creating an array where each index represents a second in time and populate the array based on Teemo’s attacks. After that, we count the total time the enemy is poisoned. However, this approach is not efficient and is impractical for large values.

Efficient Approach: Iterating through Attack Times

We can solve this problem more efficiently without simulating every second. Instead, we iterate through the attack times in timeSeries. For each attack time, we can add the duration to a total, but we need to consider that the poison effect might refresh before the duration of the previous attack ends. To account for this, we calculate the minimum of the duration and the difference between the current attack time and the previous attack time.

Let’s delve into the Python code for this approach:

def findPoisonedDuration(timeSeries, duration):
    if not timeSeries:
        return 0
    
    total_poisoned_time = 0
    
    for i in range(1, len(timeSeries)):
        time_diff = timeSeries[i] - timeSeries[i-1]
        total_poisoned_time += min(time_diff, duration)
        
    # Adding duration for the last attack
    total_poisoned_time += duration
    
    return total_poisoned_time

This approach has a time complexity of O(n), where n is the length of the input array timeSeries.

Code Optimization:

We can further optimize the code by reducing the number of calculations in the loop. We can add duration to the total poisoned time for each attack and subtract the overlap time when the poison effect refreshes.

def findPoisonedDuration(timeSeries, duration):
    if not timeSeries:
        return 0
    
    total_poisoned_time = duration * len(timeSeries)
    
    for i in range(1, len(timeSeries)):
        overlap = duration - (timeSeries[i] - timeSeries[i-1])
        if overlap > 0:
            total_poisoned_time -= overlap
    
    return total_poisoned_time

This optimized approach still has a time complexity of O(n), but with slightly fewer calculations inside the loop.

Conclusion:

The Teemo Attacking problem is an interesting problem that requires a combination of array traversal and basic mathematical calculations to reach an efficient solution. Through this problem, one can understand the importance of analyzing the given data and applying simple math to avoid unnecessary computations. By optimizing the way we calculate the total poisoned duration, we can arrive at a solution that is both efficient and clean. This problem serves as a good example to illustrate how sometimes a more efficient algorithm can be achieved by carefully analyzing the problem and employing simple math rather than relying on complex data structures or algorithms.