Teemo Attacking

Easy

Asked by:

38 views

Topics:

ArraysGreedy Algorithms

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 <= 10⁴
0 <= timeSeries[i], duration <= 10⁷
timeSeries is sorted in non-decreasing order.

Try coding it in LeetCode

Teemo Attacking

Easy

Asked by:

38 views

Topics:

ArraysGreedy Algorithms

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 <= 10⁴
0 <= timeSeries[i], duration <= 10⁷
timeSeries is sorted in non-decreasing order.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `timeSeries` array be empty, and if so, what should the return value be?
What is the range of values for the elements in the `timeSeries` array, and the value of `duration`? Can they be negative or zero?
Are the elements in the `timeSeries` array guaranteed to be sorted in ascending order?
If there are overlapping attack durations (e.g., attack starts before the previous one ends), how should the total duration be calculated?
Could you provide a concrete example, including edge cases, to illustrate the expected behavior of the function?

Brute Force Solution

Approach

Imagine Teemo is attacking at different times and each attack lasts for a certain duration. The brute force method calculates the total damage duration by considering each attack independently and summing the full duration of each, then correcting for any overlaps.

Here's how the algorithm would work step-by-step:

Start by assuming each attack lasts its full duration and add those durations together.
Go through each pair of attacks in the order they happened.
For each pair, check if the second attack happened before the first attack's duration ended.
If there was overlap, reduce the total duration by the amount of the overlap.
Once every pair of attacks has been checked, the result is the total damage duration.

Code Implementation

def teemo_attacking_brute_force(attack_times, duration):
    total_damage_duration = 0
    # Add the duration of each attack to total_damage_duration initially
    for _ in attack_times:
        total_damage_duration += duration

    # Now correct for overlaps by checking all pairs of attacks
    for first_attack_index in range(len(attack_times) - 1):

        for second_attack_index in range(first_attack_index + 1, len(attack_times)):

            # Check if the second attack happens before the first attack ends.
            if attack_times[second_attack_index] < attack_times[first_attack_index] + duration:
                overlap = attack_times[first_attack_index] + duration - attack_times[second_attack_index]

                # Reduce the total damage by the amount of the overlap.
                total_damage_duration -= overlap

    return total_damage_duration

Big(O) Analysis

Time Complexity

O(n²) – The described solution first iterates through the entire input of size n (attack times) to sum the individual attack durations. Then, it iterates through each pair of attacks to check for overlaps. This involves comparing each attack with every other attack that follows it. In the worst case, this results in roughly n * (n-1) / 2 comparisons, which is a quadratic relationship with the input size. Thus, the overall time complexity is O(n²).

Space Complexity

O(1) – The algorithm iterates through pairs of attack times to calculate the total damage duration, adjusting for overlaps. It only uses a few integer variables to track the current attack times and the total duration, regardless of the number of attacks. No auxiliary data structures such as lists or hash maps are created. Therefore, the space complexity is constant, or O(1), as it does not depend on the input size N.

Optimal Solution

Approach

The key is to avoid unnecessary calculations by figuring out how long Teemo's attack affects the target based on the time between attacks. We can determine the total duration by adding up the non-overlapping durations of each attack, taking into account the overlap.

Here's how the algorithm would work step-by-step:

Start with a total duration of zero.
Look at the first attack and its duration.
Check the time of the next attack. If it happens before the previous attack's effect wears off, calculate the actual extra time added by the current attack (the difference between the current attack time and the previous attack end time).
If the next attack happens after the previous attack's effect has worn off, just add the full duration of the current attack to the total duration.
Keep checking the attacks one at a time and adding either the full attack duration or the reduced duration as needed.
The final total will be the total time the target is affected by Teemo's attacks.

Code Implementation

def teemo_attacking(attack_times, duration):
    total_affected_duration = 0
    number_of_attacks = len(attack_times)

    if number_of_attacks == 0:
        return 0

    # Initialize previous attack end time
    previous_attack_end_time = attack_times[0] + duration
    total_affected_duration += duration

    for i in range(1, number_of_attacks):
        current_attack_time = attack_times[i]

        # If the current attack starts before the previous attack ends
        if current_attack_time < previous_attack_end_time:
            # Only add the non-overlapping duration
            total_affected_duration += current_attack_time + duration - previous_attack_end_time

        else:
            # Add the full duration of the current attack
            total_affected_duration += duration

        # Update the previous attack end time
        previous_attack_end_time = current_attack_time + duration

    return total_affected_duration

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the timeSeries array once, where n is the number of elements in the array (representing the attack times). In each iteration, a constant number of operations (comparisons and additions) are performed to determine the effective duration of each attack and update the total duration. Therefore, the time complexity is directly proportional to the number of attack times, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm iterates through the input array 'timeSeries' without using any auxiliary data structures that scale with the input size N (where N is the number of attacks). It uses a few variables like 'total_duration', and possibly a temporary variable to store the previous attack end time, but the number of these variables remains constant irrespective of the size of the input 'timeSeries'. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty timeSeries array	Return 0 since no poisoning occurs.
Null timeSeries array	Throw an IllegalArgumentException or return 0 after checking for null.
Duration is zero or negative	If duration is 0, return 0; if negative, throw an exception or return 0 after handling it.
Single element in timeSeries	Return the duration, as that's the total poisoning time.
Large timeSeries array (performance)	Use an iterative approach to avoid stack overflow and ensure linear time complexity for optimal scaling.
timeSeries contains duplicate timestamps	The algorithm should correctly handle overlapping attacks by calculating the difference between the sorted timestamps.
timeSeries is already sorted in descending order or has no specific order.	Sort timeSeries array in ascending order before processing to ensure correct calculation of poisoned duration.
Integer overflow when calculating total duration	Use long data type to store the total duration to prevent integer overflow.

Empty timeSeries array

How to Handle:

Return 0 since no poisoning occurs.

Null timeSeries array

How to Handle:

Throw an IllegalArgumentException or return 0 after checking for null.

Duration is zero or negative

How to Handle:

If duration is 0, return 0; if negative, throw an exception or return 0 after handling it.

Single element in timeSeries

How to Handle:

Return the duration, as that's the total poisoning time.

Large timeSeries array (performance)

How to Handle:

Use an iterative approach to avoid stack overflow and ensure linear time complexity for optimal scaling.

timeSeries contains duplicate timestamps

How to Handle:

The algorithm should correctly handle overlapping attacks by calculating the difference between the sorted timestamps.

timeSeries is already sorted in descending order or has no specific order.

How to Handle:

Sort timeSeries array in ascending order before processing to ensure correct calculation of poisoned duration.

Integer overflow when calculating total duration

How to Handle:

Use long data type to store the total duration to prevent integer overflow.