Minimum Health to Beat Game

Medium

Asked by:

9 views

Topics:

ArraysGreedy Algorithms

You are playing a game that consists of n levels. You are given a 0-indexed integer array damage where damage[i] is the amount of health you will lose to complete the i^th level.

You are also given an integer armor. You may use your armor at most once during the game on any level which will protect you from at most armor damage. If the level has damage strictly less than armor, you are protected from all the damage.

Return the minimum health you need to start with to beat all the n levels.

Example 1:

Input: damage = [2,7,4,3], armor = 7
Output: 10
Explanation:
Choose protecting level 1 with armor.
Minimum health to start with = 2 + (7 - 7) + 4 + 3 = 10.

Example 2:

Input: damage = [2,5,3,4], armor = 7
Output: 12
Explanation:
Choose protecting level 1 with armor.
Minimum health to start with = 2 + (5 - 7) + 3 + 4 = 2 + 0 + 3 + 4 = 9.

Example 3:

Input: damage = [3,3,3], armor = 0
Output: 9
Explanation:
You do not have armor, so you cannot reduce the damage at any level.
Minimum health to start with = 3 + 3 + 3 = 9.

Constraints:

1 <= damage.length <= 10⁵
0 <= damage[i] <= 10⁵
0 <= armor <= 10⁵

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:

What is the range of possible damage values in the input array? Can they be negative or zero?
If it's impossible to beat the game regardless of initial health, what should I return? Is there a specific error code or value?
Is the input array guaranteed to be non-empty, or should I handle the case where the array is empty or null?
If multiple initial health values would allow me to beat the game, should I return the absolute minimum value?
Are the damage values integers?

Brute Force Solution

Approach

Imagine you're trying to find the smallest amount of starting health you need to survive a game where you encounter a series of challenges that either hurt or heal you. The brute force way is to simply guess a starting health, play the game, and see if you survive. If you don't, guess a higher starting health and try again until you find one that works.

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

Start by guessing a very small amount for your initial health.
Now, simulate playing the entire game with that starting health.
At each challenge, subtract the damage (if it's a bad challenge) or add the healing (if it's a good challenge) to your current health.
If at any point during the game your health drops to zero or below, you lose. That means your initial guess was too low.
If you make it through the entire game without your health dropping to zero or below, you win! However, your initial guess might be higher than necessary.
If your initial guess was too low, increase your guess by a small amount and repeat the process from step 2.
If your initial guess worked, decrease your guess by a small amount and repeat the process from step 2 to see if an even smaller starting health would work.
Continue adjusting your guesses higher or lower until you find the absolute smallest starting health that lets you win the game.

Code Implementation

def minimum_health_to_beat_game_brute_force(health_changes):
    initial_health = 1
    step = 1

    while True:
        current_health = initial_health
        game_won = True

        for health_change in health_changes:
            current_health += health_change

            if current_health <= 0:
                game_won = False
                break

        if game_won:
            # Found a health that works, try lower
            test_health = initial_health - step
            current_health = test_health
            test_game_won = True

            for health_change in health_changes:
                current_health += health_change

                if current_health <= 0:
                    test_game_won = False
                    break

            if test_game_won:
                # Trying lower health succeeded, lets decrease the initial
                initial_health -= step
            else:
                # Lower health failed. Initial health is the min
                return initial_health
                
        else:
            # Guess was too low, increase health.
            initial_health += step

Big(O) Analysis

Time Complexity

O(n*m) – The outer loop in the brute force approach iteratively guesses starting health values until the minimum is found. Let 'm' represent the range or number of starting health guesses needed to converge on the minimum required health. For each guessed starting health, the game simulation iterates through 'n' challenges. Therefore, the time complexity is proportional to the number of guesses multiplied by the number of challenges, resulting in O(n*m). In the worst-case scenario, 'm' could be proportional to 'n' (for example, if the cumulative damage/healing is linearly dependent on 'n'), resulting in a complexity closer to O(n^2), but without more assumptions about the nature of health changes, we have to express it as O(n*m).

Space Complexity

O(1) – The algorithm simulates the game repeatedly by guessing a starting health. It only needs to store a few variables such as the current health and the best guess so far. The space required for these variables remains constant irrespective of the number of challenges (N) in the game. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To figure out the minimum health needed, we don't actually simulate playing the game. Instead, we work backwards and calculate the needed health in reverse order of levels, figuring out the minimum health needed to survive each encounter. This helps us efficiently arrive at the initial health required.

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

Start by looking at the health drain of the very last level.
Figure out the minimum health you need to have *before* that last level to survive it. This would be 1 plus the health drain of the last level (since you need to have at least 1 health point after the level).
Now, move to the second-to-last level and consider its health drain.
If the health drain of the second-to-last level is positive, then you need to add it to your 'minimum health before the last level' value. If the drain is negative (meaning you gain health), check if the gain is enough that you can lower your minimum health needed. In other words, if the health gain is greater than the current minimum, then set it to 1 because no matter what, it can't be 0.
Repeat this process, working backwards from the last level to the first level.
At each level, calculate the health needed *before* that level to survive the remaining levels.
The final health you calculate at the very first level is the minimum initial health you need to start the game and win.

Code Implementation

def minimum_health_to_beat_game(health_drain):
    levels_count = len(health_drain)
    
    # Initialize min health needed after last level.
    minimum_health_needed = 1

    for i in range(levels_count - 1, -1, -1):
        # If health drain is positive, health is needed.
        if health_drain[i] >= 0:
            minimum_health_needed += health_drain[i]

        else:
            # Check if health gain reduces minimum needed.
            if -health_drain[i] >= minimum_health_needed:
                minimum_health_needed = 1

    return minimum_health_needed

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the health array once, from the last element to the first. For each level, it performs a constant number of operations: calculating the minimum health required before that level based on the health drain at that level and the health needed for subsequent levels. The cost is directly proportional to the number of levels, n. Therefore, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm calculates the minimum health needed by iterating through the levels in reverse, but it does not use any auxiliary data structures that scale with the number of levels. It only stores a few variables to keep track of the current minimum health required, and these variables take up a constant amount of space regardless of the input size N (the number of levels). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty damage array	Return 1 if the array is null or empty as no damage is taken, requiring only 1 initial health.
Array with a single element	Return damage[0] + 1, since you need to survive the first and only stage.
Large array (performance considerations)	Ensure the algorithm has a time complexity that scales reasonably, ideally O(n) or O(n log n), to avoid timeouts.
All damage values are zero	Return 1 since no health is lost in any stage.
Damage values contain negative numbers	Treat negative damage as healing, and reduce the required initial health accordingly.
Extreme damage values leading to potential integer overflow	Use long data type or appropriate overflow detection and handling mechanisms.
The total damage exceeds the maximum representable integer value	Handle potential integer overflow by either using a larger data type or clamping the health to the maximum possible value.
Damage values include floating-point numbers	Convert all damage values to integers by rounding up (ceiling function) before calculating health to avoid precision issues and ensure the health is sufficient for the integer damage being taken.

Null or empty damage array

How to Handle:

Return 1 if the array is null or empty as no damage is taken, requiring only 1 initial health.

Array with a single element

How to Handle:

Return damage[0] + 1, since you need to survive the first and only stage.

Large array (performance considerations)

How to Handle:

Ensure the algorithm has a time complexity that scales reasonably, ideally O(n) or O(n log n), to avoid timeouts.

All damage values are zero

How to Handle:

Return 1 since no health is lost in any stage.

Damage values contain negative numbers

How to Handle:

Treat negative damage as healing, and reduce the required initial health accordingly.

Extreme damage values leading to potential integer overflow

How to Handle:

Use long data type or appropriate overflow detection and handling mechanisms.

The total damage exceeds the maximum representable integer value

How to Handle:

Handle potential integer overflow by either using a larger data type or clamping the health to the maximum possible value.

Damage values include floating-point numbers

How to Handle:

Convert all damage values to integers by rounding up (ceiling function) before calculating health to avoid precision issues and ensure the health is sufficient for the integer damage being taken.