Scale Engineer

Teemo Attacking

Easy
#0482Time: 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: 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.1 company
Data structures
Array
Companies
Riot Games

Prompt

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 <= 104
  • 0 <= timeSeries[i], duration <= 107
  • timeSeries is sorted in non-decreasing order.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem