LeetCode 2214 - Minimum Health to Beat Game

The problem presents a sequential game consisting of n levels, where each level inflicts a specific amount of damage to the player. You are given a list damage where damage[i] represents the damage from level i.

leetcodemediumarraygreedy

LeetCode Problem 2214

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem presents a sequential game consisting of n levels, where each level inflicts a specific amount of damage to the player. You are given a list damage where damage[i] represents the damage from level i. Additionally, the player has an armor ability that can be used once to reduce the damage of a single level by up to the armor value.

The goal is to determine the minimum initial health required so that the player can survive through all levels in order, keeping health strictly positive at every step. The output is therefore a single integer representing this minimum health.

Important observations from the constraints and problem statement include:

  • The number of levels n can be as large as 10^5, so any solution that is quadratic or involves checking all possible sequences is infeasible.
  • Damage values and armor can be zero. A level might deal zero damage, or armor might provide no reduction.
  • The armor should ideally be used on the level with the maximum damage, because using it elsewhere would not minimize the total starting health. This is a key insight that simplifies the problem.
  • The health must remain strictly positive, so even after reducing a level’s damage with armor, at least 1 health is required at the end.

Edge cases to consider include:

  • All damage values are zero, with any armor value. The player only needs 1 health.
  • Armor is zero, which means the player simply takes all damage.
  • Only one level exists, where armor might completely absorb it.

Approaches

Brute Force

The brute force approach would attempt every possible level to apply the armor. For each level, simulate the game from start to finish, apply armor on that level, and compute the required starting health to survive all levels. Finally, pick the minimum starting health across all simulations.

While this approach is correct, it is inefficient because for each level you must iterate through all n levels to calculate cumulative health, giving a time complexity of O(n^2). With n up to 10^5, this is far too slow.

Optimal Approach

The key observation is that armor should be applied to the level with the maximum damage. By reducing the largest single damage, you minimize the total sum of health lost. Therefore, the optimal starting health is simply the sum of all damage minus the reduction from armor, plus 1 to ensure strictly positive health at the end.

Formally, the algorithm is:

  1. Compute the sum of all damage values.
  2. Find the maximum damage value.
  3. Calculate min_health = total_damage - min(max_damage, armor) + 1.

This approach is efficient, runs in a single pass, and works for all input sizes.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Simulate game for armor on each level
Optimal O(n) O(1) Sum damage and subtract the best use of armor

Algorithm Walkthrough

  1. Initialize total_damage to 0 and max_damage to 0.
  2. Iterate through each level in the damage array.
  3. For each level, add damage[i] to total_damage.
  4. Update max_damage if damage[i] is larger than the current max_damage.
  5. After iterating, calculate the reduction from armor as the minimum of armor and max_damage.
  6. Compute the minimum starting health as total_damage - reduction + 1.
  7. Return the calculated minimum health.

Why it works: The invariant is that applying armor to the level with the highest damage maximizes the benefit of the armor. Summing all damage accounts for all health lost if no armor is used, and subtracting the armor reduction ensures we reduce health loss optimally. Adding 1 guarantees the health never drops to zero.

Python Solution

from typing import List

class Solution:
    def minimumHealth(self, damage: List[int], armor: int) -> int:
        total_damage = 0
        max_damage = 0
        
        for d in damage:
            total_damage += d
            max_damage = max(max_damage, d)
        
        reduction = min(max_damage, armor)
        min_health = total_damage - reduction + 1
        
        return min_health

The implementation iterates through damage once, keeping track of the cumulative damage and the maximum damage. After the loop, it applies the optimal use of armor and ensures that at least 1 health remains at the end.

Go Solution

func minimumHealth(damage []int, armor int) int64 {
    var totalDamage int64 = 0
    var maxDamage int = 0

    for _, d := range damage {
        totalDamage += int64(d)
        if d > maxDamage {
            maxDamage = d
        }
    }

    reduction := maxDamage
    if armor < maxDamage {
        reduction = armor
    }

    return totalDamage - int64(reduction) + 1
}

In Go, we use int64 for totalDamage to avoid integer overflow, since n and damage[i] can be up to 10^5. The rest of the logic mirrors the Python solution, iterating once and computing the reduction.

Worked Examples

Example 1

damage = [2,7,4,3], armor = 4

Level Damage Max Damage Total Damage Reduction Remaining Health Needed
0 2 2 2
1 7 7 9
2 4 7 13
3 3 7 16

Reduction = min(7,4) = 4

Minimum Health = 16 - 4 + 1 = 13

Example 2

damage = [2,5,3,4], armor = 7

Max damage = 5, reduction = min(5,7) = 5

Total damage = 2+5+3+4 = 14

Minimum Health = 14 - 5 + 1 = 10

Example 3

damage = [3,3,3], armor = 0

Max damage = 3, reduction = min(3,0) = 0

Total damage = 9

Minimum Health = 9 - 0 + 1 = 10

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the damage array to compute sum and max
Space O(1) Only two variables tracked regardless of input size

This is efficient and scales to the maximum constraint n = 10^5.

Test Cases

# Provided examples
assert Solution().minimumHealth([2,7,4,3], 4) == 13  # Armor used on 4 damage
assert Solution().minimumHealth([2,5,3,4], 7) == 10  # Armor used on 5 damage
assert Solution().minimumHealth([3,3,3], 0) == 10    # No armor

# Edge cases
assert Solution().minimumHealth([0,0,0], 10) == 1     # No damage, minimum health is 1
assert Solution().minimumHealth([10], 10) == 1       # Single level, armor absorbs all damage
assert Solution().minimumHealth([10], 5) == 6        # Single level, partial armor
assert Solution().minimumHealth([1]*100000, 0) == 100001  # Large input, no armor
assert Solution().minimumHealth([100000]*100000, 100000) == 9999900001  # Large numbers
Test Why
[2,7,4,3], 4 Normal case with partial armor usage
[2,5,3,4], 7 Normal case, armor exceeds max damage
[3,3,3], 0 No armor
[0,0,0], 10 No damage, health should be minimum 1
[10], 10 Single level, armor fully absorbs
[10], 5 Single level, armor partially absorbs
[1]*100000, 0 Stress test with maximum n
[100000]*100000, 100000 Stress test with maximum values

Edge Cases

Edge Case 1: Armor is zero

If armor = 0, the algorithm naturally reduces to summing all damage and adding 1, which is correct since armor provides no benefit. This prevents negative reduction or miscalculations.

Edge Case 2: Single level game

With n = 1, the algorithm correctly identifies whether armor can completely absorb the single damage. The min(max_damage, armor) ensures proper computation.

Edge Case 3: All zero damage

If every level has damage[i] = 0, the algorithm returns 1 as the minimum starting health. This ensures health remains positive even if no damage is taken, satisfying the game requirement.