Teemo Attacking

In this blog, you will see how to solve Leetcode problem #495.

Introduction

 

In this article, we will sove the leetcode problem #495, Teemo Attacking. The problem statement goes like this:

 

In LOL world, there is a hero called Teemo and his attacks can poison his enemy, Ashe. Now, given Teemo's attacking ascending time series towards Ashe and the poisoning time duration per Teemo's attacking, you need to output the total time that Ashe is in a poisoned condition. 

 

You may assume that Teemo attacks at the very beginning of a specific time point, and puts Ashe in a poisoned condition immediately. For example, if the time series is [ 1, 4 ] and the duration is 2, then the poisoned duration will be 4. At time point 1, Teemo starts attacking Ashe and  poisons Ashe  immediately.This poisoned status will last 2 seconds until the end of time point 2. And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in a poisoned status for another 2 seconds.So you finally need to output 4.

static void Main(string[] args)
{
    var result = findPoisonedDuration(new int[] { 1, 4 }, 2);
    //result = 4
    result = findPoisonedDuration(new int[] { 1, 2 }, 2);
    //result = 3
}

You may assume the length of given time series array won't exceed 10000. You may also assume the numbers in the Teemo's attacking time series and his poisoning time duration per attacking are non-negative integers, which won't exceed 10,000,000.

 

Solution

 

The most naive approach for problems like this is dynamic programming, in which we will loop over the time series and check whether current time series is more than the duration or not. And finally we keep adding the duration to get the total duration. Here is the C# code for the approach,

static int findPoisonedDuration(int[] timeSeries, int duration)
{
    if (timeSeries == null || timeSeries.Length == 0 || duration == 0)
    {
        return 0;
    }
    int totalDuration = 0;
    for (int i = 0; i < timeSeries.Length - 1; i++)
    {
        if ((timeSeries[i + 1] - timeSeries[i]) >= duration)
        {
            totalDuration += duration;
        }
        else
        {
            totalDuration += (timeSeries[i + 1] - timeSeries[i]);
        }
    }
    totalDuration += duration;
    return totalDuration;
}