algoadvance

In the game, Hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly duration seconds. More attacks may follow, and the poison’s timer resets with each subsequent attack. However, if Teemo attacks again before the poison effect fades, the timer will reset, and the poison effect will extend.

You are given a non-decreasing integer array timeSeries, where timeSeries[i] denotes that Teemo attacks Ashe at time timeSeries[i], and an integer duration.

Return the total number of seconds that Ashe is poisoned.

Clarifying Questions

  1. Can timeSeries contain duplicate times?
    • No, all values in timeSeries are distinct and non-decreasing.
  2. Is timeSeries guaranteed to be sorted in non-decreasing order?
    • Yes, timeSeries is already sorted in non-decreasing order.
  3. What are the constraints on the values of the elements in timeSeries and duration?
    • 1 <= timeSeries.length <= 10000
    • 0 <= timeSeries[i] <= 10^7
    • 1 <= duration <= 10^7

Strategy

We need to compute the total duration for which Ashe is poisoned. Here’s the approach:

  1. Initialize total_poisoned_duration to 0.
  2. Iterate through timeSeries array to calculate how long Ashe remains poisoned.
    • For each attack at time timeSeries[i], calculate the overlap time with the previous attack if any.
    • Add the minimum of duration and the time difference between the current attack and the previous attack to the total poisoned duration.
  3. The last attack will always contribute a full duration to the total duration.
  4. Return the computed total poisoned duration.

Time Complexity

Code

def findPoisonedDuration(timeSeries, duration):
    if not timeSeries:
        return 0
    
    total_poisoned_duration = 0
    
    for i in range(1, len(timeSeries)):
        # Calculate the minimum poison duration between attacks
        total_poisoned_duration += min(duration, timeSeries[i] - timeSeries[i-1])
    
    # Always add the duration for the last attack
    total_poisoned_duration += duration
    
    return total_poisoned_duration

# Example usage
timeSeries = [1, 4]
duration = 2
print(findPoisonedDuration(timeSeries, duration))  # Output: 4

timeSeries = [1, 2]
duration = 2
print(findPoisonedDuration(timeSeries, duration))  # Output: 3

This solution efficiently calculates the total poisoned duration using a single pass through the timeSeries array, ensuring a linear runtime complexity.

Try our interview co-pilot at AlgoAdvance.com