Teemo Attacking

EASY

Description

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.

Approaches

Checkout 3 different approaches to solve Teemo Attacking. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Simulation using a Set

This approach simulates the poisoning process second by second. We use a data structure, like a HashSet, to keep track of every individual second that Ashe is poisoned.

Algorithm

Initialize an empty HashSet called poisonedSeconds.
For each attack time t in timeSeries:
- Loop from i = 0 to duration - 1.
- Add t + i to the poisonedSeconds set.
Return the size of poisonedSeconds.

We iterate through each attack time t in the timeSeries array. For each attack, we start a nested loop that runs for duration seconds. In this inner loop, we add each second from t to t + duration - 1 into a HashSet. The HashSet automatically handles duplicates, so if a second is already poisoned, adding it again has no effect. After iterating through all the attacks, the total poisoned time is simply the final size of the HashSet.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) {
            return 0;
        }
        Set<Integer> poisonedSeconds = new HashSet<>();
        for (int t : timeSeries) {
            for (int i = 0; i < duration; i++) {
                poisonedSeconds.add(t + i);
            }
        }
        return poisonedSeconds.size();
    }
}

Complexity Analysis

Time Complexity: O(N * D), where N is the length of `timeSeries` and D is `duration`. We have a nested loop structure where for each of the N attacks, we iterate D times. This is very slow if D is large.Space Complexity: O(N * D) in the worst case, where N is the length of `timeSeries` and D is `duration`. The `HashSet` can store up to N * D unique seconds if all poison intervals are disjoint, which can lead to excessive memory usage.

Pros and Cons

Pros:

Simple to understand and implement.
Directly models the problem description.

Cons:

Highly inefficient in terms of both time and space.
Will likely result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error for the given constraints.

Code Solutions

Checking out 4 solutions in different languages for Teemo Attacking. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Teemo Attacking

Data Structures:

Array

Companies:

Riot Games |