495. Teemo Attacking

EasyArraySimulation

Problem Description

In this problem, we are given a scenario where a character named Teemo is attacking another character named Ashe with poison attacks. When an attack occurs, it poisons Ashe for a fixed duration. Each attack time is recorded in an array called timeSeries, and this array is in non-decreasing order, which means the attacks are listed in the order they happened and no attack happens before the previous one. The duration is a fixed amount of time that the poison lasts after each attack. If Ashe gets attacked again before the previous poison has worn off, the poison duration is reset to last for duration more seconds from the time of the new attack.

Our goal is to calculate the total number of seconds Ashe is poisoned. Since an attack at second t means Ashe is poisoned up to t + duration - 1, we must be careful not to count any time twice if the poison effect from a previous attack is extended by a subsequent attack before it has ended.

Intuition

To solve the problem, we need to calculate the periods Ashe is poisoned without counting any seconds multiple times. We initialize the total poisoned time with duration to account for the first attack, assuming there is at least one attack.

Then, we iterate through each pair of consecutive attacks (using a handy Python function called pairwise from the itertools module, that allows us to consider the attack at timeSeries[i] and timeSeries[i+1] at the same time). For each pair of attacks, we have two cases:

If the next attack happens after the current poison effect has ended, Ashe will be poisoned for a full duration again starting from the new attack.
If the next attack happens before the current poison has worn off, we only need to extend the poison effect to last duration seconds after this new attack, which may be less than a full duration.

The amount by which we extend the poison effect can be found by taking the minimum of duration and the difference between the current and next attack times, b - a. This ensures that if the new attack happens very shortly after the first one, we don't count more than the total duration for the poison effect that’s been reset.

Finally, we sum up all the extensions for every pair of attacks to get the total time. The result is the total number of seconds that Ashe stays poisoned.

Solution Approach

The solution uses a straightforward algorithm to implement the logic explained in the intuition:

Initialize a variable ans with the value of duration. This is to account for the initial state when Teemo attacks Ashe once. The postulated scenario ensures there is at least one attack. Thus, Ashe is at minimum poisoned for the length of duration.
Iterate through pairs of consecutive attacks. Python's pairwise function is used here from the itertools module, which takes an iterable and returns a new iterator over pairs of consecutive elements. For a list timeSeries, pairwise(timeSeries) yields (timeSeries[0], timeSeries[1]), (timeSeries[1], timeSeries[2]), and so on.
For each consecutive pair (a, b) of timeSeries, calculate the time the poison will last. If b - a >= duration, it means that the poison from the first attack would have worn off before the second attack occurs. If b - a < duration, the second attack effectively resets the timer, and the poison now extends b - a seconds past the time of the second attack.
For each pair (a, b), add the minimum of duration and b - a to ans. This accounts for extending the poison duration correctly without double-counting any seconds.
After processing all pairs, ans holds the total time Ashe is poisoned, which is returned as the result.

The algorithm is efficient as it only goes through the list of attack times once, with a time complexity of O(n), where n is the number of attack times in timeSeries. No additional space apart from the input and a few variables is used, resulting in O(1) space complexity. The pairwise function is not included in the space complexity as it only returns an iterator and doesn't store the pairs in memory.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have timeSeries = [1, 4, 5] and duration = 2. This means Teemo attacks Ashe at times 1, 4, and 5, and each poison lasts for 2 seconds.

We start by initializing ans as duration. Therefore, ans = 2.
Iterate using pairwise, which will produce pairs (1, 4) and (4, 5) for our example.
For the pair (1, 4), we see that b - a = 4 - 1 = 3, which is greater than duration = 2. This means the poison had worn off before the second attack. Thus, we add the full duration to ans. Now, ans = ans + duration = 2 + 2 = 4.
For the next pair (4, 5), b - a = 5 - 4 = 1, which is less than duration. The second attack happens before the poison from the previous attack has worn off. We extend the poison duration by the amount b - a, which is 1 in this case. Hence, ans = ans + (b - a) = 4 + 1 = 5.
There are no more pairs. The total time Ashe is poisoned is stored in ans, which is 5 seconds.

To understand the final result, let's visualize the timeline:

First attack at time 1, poison lasts until the end of time 2.
Second attack at time 4, poison lasts until the end of time 5.
Third attack at time 5, extends the poison from the end of time 5 to the end of time 6.

So visually:

Time:        1 2 3 4 5 6
Poison:      X X - X X X 
Total time poisoned = 1-2 + 4-6 = 2 + 2 = 4 seconds.

Thus the total time poisoned is 5 seconds as calculated. This example confirms that the algorithm correctly calculates the total time Ashe is poisoned without double-counting any seconds.

Solution Implementation

1from typing import List
2from itertools import tee
3
4class Solution:
5    def findPoisonedDuration(self, time_series: List[int], duration: int) -> int:
6        # Helper function to mimic the pairwise utility, yielding consecutive pairs from time_series
7        def pairwise(iterable):
8            a, b = tee(iterable)
9            next(b, None)
10            return zip(a, b)
11
12        # If there are no time stamps, the poisoned duration is 0
13        if not time_series:
14            return 0
15          
16        # Initialize total poisoned duration with the duration of the last poisoning event
17        total_duration = duration
18      
19        # Calculate the poisoned duration by comparing consecutive poison times
20        for start, end in pairwise(time_series):
21            time_diff = end - start
22            total_duration += min(duration, time_diff)
23          
24        return total_duration
25

1class Solution {
2    // Method to find total time for which a character remains poisoned
3    public int findPoisonedDuration(int[] timeSeries, int duration) {
4        // Length of the timeSeries array
5        int n = timeSeries.length;
6      
7        // If there are no attacks, return 0 as the poisoned duration
8        if (n == 0) {
9            return 0;
10        }
11      
12        // Initialize total poisoned duration with the duration of the first attack
13        int totalPoisonedDuration = duration;
14      
15        // Iterate through the time series starting from the second attack
16        for (int i = 1; i < n; ++i) {
17            // Calculate the time difference between current and previous attack
18            int timeDifference = timeSeries[i] - timeSeries[i - 1];
19          
20            // If the time difference is less than the duration of the poison,
21            // it means the poison effect would have been refreshed and not lasted full duration,
22            // so add the time difference, otherwise add the full duration
23            totalPoisonedDuration += Math.min(duration, timeDifference);
24        }
25      
26        // Return the total duration for which the character was poisoned
27        return totalPoisonedDuration;
28    }
29}
30

1#include <vector>
2#include <algorithm> // For std::min function
3
4class Solution {
5public:
6    int findPoisonedDuration(std::vector<int>& timeSeries, int duration) {
7        // The total poison duration starts with the duration of the first attack,
8        // as there can be no overlap in this case
9        int totalPoisonDuration = duration;
10      
11        // Number of time points in the series
12        int numOfTimePoints = timeSeries.size();
13      
14        // Loop through all the time points starting from the second one
15        for (int i = 1; i < numOfTimePoints; ++i) {
16            // Calculate the poisoned time by the current attack.
17            // If the time difference between the current attack and the previous one
18            // is less than the duration, the poison duration is shortened to this time difference 
19            // to avoid counting the overlapping time more than once.
20            totalPoisonDuration += std::min(duration, timeSeries[i] - timeSeries[i - 1]);
21        }
22      
23        // Return the total calculated poison duration
24        return totalPoisonDuration;
25    }
26};
27

1function findPoisonedDuration(timeSeries: number[], duration: number): number {
2    // 'n' represents the total number of time points in the timeSeries array.
3    const n = timeSeries.length;
4  
5    // If there are no time points, the poisoned duration is 0.
6    if (n === 0) return 0;
7
8    // 'totalDuration' will accumulate the total duration for which the target is poisoned.
9    let totalDuration = 0;
10
11    // Iterate over the time points to calculate the poisoned duration.
12    for (let i = 0; i < n - 1; ++i) {
13        // Calculate the time difference between the current and the next time point.
14        const timeDifference = timeSeries[i + 1] - timeSeries[i];
15
16        // If the time difference is less than the 'duration',
17        // add this time difference to 'totalDuration' as the poison
18        // overlaps. Otherwise, add the full 'duration'.
19        totalDuration += Math.min(duration, timeDifference);
20    }
21
22    // Add the 'duration' of the last poisoning effect,
23    // since it will last the full 'duration' time.
24    totalDuration += duration;
25
26    // Return the sum of all the durations for which the target is poisoned.
27    return totalDuration;
28}
29

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(N), where N is the length of the timeSeries array. This is because the code iterates through the array once using a for loop with the pairwise function, which generates a new pair for consecutive elements on each iteration.

Space Complexity

The space complexity of the code is O(1). Regardless of the size of the input list, the only extra space required is for the variable ans. The pairwise function generates pairs on-the-fly on each iteration without storing them, thus not requiring any additional significant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: