We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Teemo Attacking

Number: 495

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Riot Games

Problem Description

Given a sorted integer array timeSeries where timeSeries[i] indicates the time Teemo attacks Ashe and an integer duration, calculate the total number of seconds that Ashe is poisoned. Each attack poisons Ashe for duration seconds, but if a new attack occurs before the previous poison effect ends, the poison timer is reset.

Key Insights

  • The poison intervals can overlap when attacks occur before the previous poison duration is complete.
  • For consecutive attacks, only a portion (min(duration, timeSeries[i+1] - timeSeries[i])) contributes additional poison time.
  • The last attack always adds the full duration since there is no subsequent attack to overlap.

Space and Time Complexity

Time Complexity: O(n) where n is the number of attacks. Space Complexity: O(1)

Solution

The solution uses a simple iterative simulation:

  1. Initialize a total counter for poisoned time.
  2. Loop through the timeSeries array (except the last element) and for each attack, add the minimum of the fixed duration and the difference between the current and next attack time.
  3. After the loop, add the full duration for the last attack as there is no follow-up attack. This approach uses only constant extra space and runs in linear time relative to the number of attacks.

Code Solutions

# Python solution for Teemo Attacking

def findPoisonedDuration(timeSeries, duration):
    # If the list is empty, return 0 as no poisoning happens
    if not timeSeries:
        return 0

    total_poisoned = 0

    # Loop through all attacks except the last one
    for i in range(len(timeSeries) - 1):
        # The effective poison time is the minimum between duration 
        # and the time difference to the next attack
        total_poisoned += min(duration, timeSeries[i+1] - timeSeries[i])
    
    # Add the full duration for the final attack
    total_poisoned += duration
    return total_poisoned

# Example usage:
# timeSeries = [1,4], duration = 2 --> Expected output: 4
print(findPoisonedDuration([1,4], 2))
← Back to All Questions