algoadvance

Leetcode 495. Teemo Attacking

Problem Statement

In the game, “League of Legends,” there is an item called “Teemo” that can poison enemies. When Teemo attacks an enemy, the enemy gets poisoned and stays poisoned for a duration given by duration seconds. If Teemo attacks again before the end of the poison duration, the poison timer is reset, and the target remains poisoned for another duration seconds.

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

Return the total time that the target is poisoned.

Example

Example 1:

Input: timeSeries = [1, 4], duration = 2
Output: 4
Explanation: At time 1, Teemo attacks and the target is poisoned for 2 seconds.
At time 4, Teemo attacks again, and the poison duration is reset for another 2 seconds.
Total poison time is 2 + 2 = 4 seconds.

Example 2:

Input: timeSeries = [1, 2], duration = 2
Output: 3
Explanation: At time 1, Teemo attacks and the target is poisoned.
At time 2, Teemo attacks again before the poison duration ends, so the poison duration is reset.
The total poison time is only extended by 1 second.

Clarifying Questions

  1. Range of Input Values:
    • What is the range of the lengths of timeSeries? (Typically constrained to keep computations feasible.)
    • What is the range for the values in timeSeries and duration?
  2. Boundary Cases:
    • What should be the output if timeSeries is empty?
  3. Non-decreasing Array:
    • Can we assume timeSeries is always sorted in non-decreasing order?

Strategy

  1. Iterating Through the Time Series:
    • Initialize totalPoisonedTime to zero.
    • Traverse through timeSeries and compute the poisoned time for each attack considering the current and the next attack.
    • Compare the difference between consecutive attack times (timeSeries[i+1] - timeSeries[i]) and duration to determine if the poison duration is completely utilized or partially overlapped.
  2. Handling Last Attack:
    • For the last attack in the series, simply add the full duration as there is no next attack to compare with.

Time Complexity

Code

#include <vector>
using namespace std;

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int totalPoisonedTime = 0;
        int n = timeSeries.size();

        for (int i = 0; i < n - 1; ++i) {
            totalPoisonedTime += min(duration, timeSeries[i+1] - timeSeries[i]);
        }

        // Add the duration for the last attack, it always lasts for 'duration' seconds
        if (n > 0) {
            totalPoisonedTime += duration;
        }

        return totalPoisonedTime;
    }
};

This solution traverses the timeSeries to calculate the total poisoned time, considering the duration overlaps properly for each attack.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI