Minimum Health to Beat Game

Medium

Amazon

1 view

Topics:

ArraysGreedy Algorithms

You are playing a game where you fight a series of enemies. Each enemy has a certain amount of damage they can inflict on you. You are given an array damage where damage[i] represents the amount of damage the i-th enemy will inflict. You start with a certain amount of health, and after each fight, your health decreases by the enemy's damage. You must have at least 1 health remaining to survive each fight.

Your goal is to determine the minimum starting health you need to have to beat all the enemies in the game. You can choose the order in which you fight the enemies. The order you fight them in will minimize the health you need, so you should pick the best order.

For example:

If damage = [2, 7, 1, 4], the minimum starting health you need is 8.
If damage = [1, 1, 1], the minimum starting health you need is 3.
If damage = [5, 2, 4, 1], the minimum starting health you need is 8.

Explain an algorithm to efficiently determine the minimum starting health required to beat the game and provide the time and space complexity. Can you give example code?

Minimum Health to Beat Game

Medium

Amazon

1 view

Topics:

ArraysGreedy Algorithms

For example:

If damage = [2, 7, 1, 4], the minimum starting health you need is 8.
If damage = [1, 1, 1], the minimum starting health you need is 3.
If damage = [5, 2, 4, 1], the minimum starting health you need is 8.

Explain an algorithm to efficiently determine the minimum starting health required to beat the game and provide the time and space complexity. Can you give example code?

Solution

Minimum Health to Beat Game

Naive Solution

A brute-force approach would involve trying different starting health values and simulating the game for each value. For each starting health, we iterate through the array of damage values. If the health drops to zero or below at any point, the current starting health is not sufficient. We would continue increasing the starting health until we find a value that allows us to survive the entire game.

This approach is inefficient because it involves repeated simulations of the game for different health values.

Optimal Solution

The key observation is that the minimum starting health required is determined by two factors:

The sum of all damage values encountered before the largest damage value. We need to survive these initial encounters.
The single largest damage value itself. Even if we can survive all the smaller damage values, we need enough health initially to survive the largest hit and still have at least 1 health left afterwards.

Therefore, the optimal strategy is to:

Find the maximum damage value in the array.
Calculate the sum of all damage values.
The minimum starting health is equal to (sum of all damage values - maximum damage value + 1).

Edge Cases:

If the damage array is empty, the minimum health is 1.
If the damage array contains only one element, the minimum health is damage[0] + 1.
If all damages are 0, the minimum health is 1.

Example

Consider the damage array [2, 7, 1, 4].

The maximum damage is 7.
The sum of all damage values is 2 + 7 + 1 + 4 = 14.
The minimum starting health is 14 - 7 + 1 = 8.

With a starting health of 8, the health progression is:

8 - 2 = 6
6 - 7 = -1 (Without the "+1", we would have died here.)
Since we remove the max value, we need 8 - 2 + 1 + 4 = 8
health - sum(damage) + max(damage) + 1

def minimumHealth(damage: list[int]) -> int:
    max_damage = 0
    total_damage = 0
    
    for d in damage:
        total_damage += d
        max_damage = max(max_damage, d)

    return total_damage - max_damage + 1

Time Complexity

The optimal solution involves iterating through the array once to find the maximum damage and calculate the sum. Therefore, the time complexity is O(n), where n is the number of damage values.

Space Complexity

The space complexity is O(1) because we only use a few constant-space variables to store the maximum damage and the sum of damage values.

Solution

Minimum Health to Beat Game

Naive Solution

This approach is inefficient because it involves repeated simulations of the game for different health values.

Optimal Solution

The key observation is that the minimum starting health required is determined by two factors:

The sum of all damage values encountered before the largest damage value. We need to survive these initial encounters.
The single largest damage value itself. Even if we can survive all the smaller damage values, we need enough health initially to survive the largest hit and still have at least 1 health left afterwards.

Therefore, the optimal strategy is to:

Find the maximum damage value in the array.
Calculate the sum of all damage values.
The minimum starting health is equal to (sum of all damage values - maximum damage value + 1).

Edge Cases:

If the damage array is empty, the minimum health is 1.
If the damage array contains only one element, the minimum health is damage[0] + 1.
If all damages are 0, the minimum health is 1.

Example

Consider the damage array [2, 7, 1, 4].

The maximum damage is 7.
The sum of all damage values is 2 + 7 + 1 + 4 = 14.
The minimum starting health is 14 - 7 + 1 = 8.

With a starting health of 8, the health progression is:

8 - 2 = 6
6 - 7 = -1 (Without the "+1", we would have died here.)
Since we remove the max value, we need 8 - 2 + 1 + 4 = 8
health - sum(damage) + max(damage) + 1

def minimumHealth(damage: list[int]) -> int:
    max_damage = 0
    total_damage = 0
    
    for d in damage:
        total_damage += d
        max_damage = max(max_damage, d)

    return total_damage - max_damage + 1

Time Complexity

The optimal solution involves iterating through the array once to find the maximum damage and calculate the sum. Therefore, the time complexity is O(n), where n is the number of damage values.

Space Complexity

The space complexity is O(1) because we only use a few constant-space variables to store the maximum damage and the sum of damage values.