Minimum Health to Beat Game solution and explanation
3 more videos on this problem
MINIMUM HEALTH TO BEAT GAME | LEETCODE 2214 | TOP AMAZON QUESTION | PYTHONCracking FAANG · 4:55 · 1K views
2214. Minimum Health to Beat Game - Week 2/5 Leetcode January ChallengeProgramming Live with Larry · 14:30 · 439 views
Minimum Health to Beat Game - LeetCode PremiumLeetCode Україна · 17:57 · 106 views
LeetCode 2214: Minimum Health to Beat GameAlitaCode · 27:34 · 17 views
The problem
You are playing a game that has n levels numbered from 0 to n - 1. You are given a 0-indexed integer array damage where damage[i] is the amount of health you will lose to complete the ith level.
You are also given an integer armor. You may use your armor ability at most once during the game on any level which will protect you from at most armor damage.
You must complete the levels in order and your health must be greater than 0 at all times to beat the game.
Return the minimum health you need to start with to beat the game.
Example 1:
Input: damage = [2,7,4,3], armor = 4 Output: 13 Explanation: One optimal way to beat the game starting at 13 health is: On round 1, take 2 damage. You have 13 - 2 = 11 health. On round 2, take 7 damage. You have 11 - 7 = 4 health. On round 3, use your armor to protect you from 4 damage. You have 4 - 0 = 4 health. On round 4, take 3 damage. You have 4 - 3 = 1 health. Note that 13 is the minimum health you need to start with to beat the game.
Example 2:
Input: damage = [2,5,3,4], armor = 7 Output: 10 Explanation: One optimal way to beat the game starting at 10 health is: On round 1, take 2 damage. You have 10 - 2 = 8 health. On round 2, use your armor to protect you from 5 damage. You have 8 - 0 = 8 health. On round 3, take 3 damage. You have 8 - 3 = 5 health. On round 4, take 4 damage. You have 5 - 4 = 1 health. Note that 10 is the minimum health you need to start with to beat the game.
Example 3:
Input: damage = [3,3,3], armor = 0 Output: 10 Explanation: One optimal way to beat the game starting at 10 health is: On round 1, take 3 damage. You have 10 - 3 = 7 health. On round 2, take 3 damage. You have 7 - 3 = 4 health. On round 3, take 3 damage. You have 4 - 3 = 1 health. Note that you did not use your armor ability.
Constraints:
n == damage.length1 <= n <= 1050 <= damage[i] <= 1050 <= armor <= 105
Approach overview
Problem Overview: You face a sequence of attacks represented by an array where damage[i] is the health lost at step i. You also have armor that can absorb up to armor damage from a single attack once. The goal is to compute the minimum starting health so that your health never drops to zero or below while processing all attacks.
Approach 1: Try Armor on Every Attack (Brute Force) (Time: O(n^2), Space: O(1))
Simulate the game while assuming the armor is used on each possible attack index. For each candidate position, iterate through the entire array, subtracting damage while applying the armor reduction on the chosen attack. Track the total damage taken and compute the minimum initial health required to survive. This works because the armor can only be used once, but recomputing the total damage for every index leads to quadratic time. The approach is easy to reason about but inefficient for large inputs.
Approach 2: Greedy – Use Armor on the Largest Attack (Time: O(n), Space: O(1))
The key observation is that armor should always be used on the largest damage value. Since it can absorb up to armor damage from a single attack, applying it anywhere else wastes potential reduction. First iterate through the array to compute the total damage using a simple running sum. At the same time track the maximum attack value. The actual reduction from armor is min(maxDamage, armor). Subtract this reduction from the total damage to get the effective damage taken.
The minimum starting health must be strictly greater than the total damage taken during the game. If the player takes D effective damage overall, they need at least D + 1 health to stay alive after the final attack. The formula becomes:
minHealth = sum(damage) - min(max(damage), armor) + 1
This greedy strategy works because the decision is globally optimal: the armor always provides the maximum benefit when applied to the largest attack. The algorithm only requires a single pass through the array and constant extra memory, making it both fast and simple. Problems like this often appear under the greedy category where the locally optimal choice leads directly to the global optimum.
Recommended for interviews: Interviewers expect the greedy observation. Brute force shows you understand the constraint that armor can be used once, but the optimal solution demonstrates the key insight: maximizing the absorbed damage by applying armor to the largest attack. The final implementation runs in O(n) time and O(1) space.
Solution
We can greedily choose to use the armor skill in the round with the highest damage. Suppose the maximum damage is mx, then we can avoid min(mx, armor) damage. Therefore, the minimum health required is sum(damage) - min(mx, armor) + 1.
The time complexity is O(n), where n is the length of the array damage. The space complexity is O(1).
class Solution:
def minimumHealth(self, damage: List[int], armor: int) -> int:
return sum(damage) - min(max(damage), armor) + 1class Solution {
public long minimumHealth(int[] damage, int armor) {
long s = 0;
int mx = damage[0];
for (int v : damage) {
s += v;
mx = Math.max(mx, v);
}
return s - Math.min(mx, armor) + 1;
}
}class Solution {
public:
long long minimumHealth(vector<int>& damage, int armor) {
long long s = 0;
int mx = damage[0];
for (int& v : damage) {
s += v;
mx = max(mx, v);
}
return s - min(mx, armor) + 1;
}
};function minimumHealth(damage: number[], armor: number): number {
let s = 0;
let mx = 0;
for (const v of damage) {
mx = Math.max(mx, v);
s += v;
}
return s - Math.min(mx, armor) + 1;
}func minimumHealth(damage []int, armor int) int64 {
var s int64
var mx int
for _, v := range damage {
s += int64(v)
mx = max(mx, v)
}
return s - int64(min(mx, armor)) + 1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Try Armor on Every Attack (Brute Force) | O(n^2) | O(1) | Useful for understanding the constraint that armor can be used once and validating the greedy insight. |
| Greedy – Use Armor on Largest Damage | O(n) | O(1) | Optimal solution for production and interviews. One pass to compute total damage and maximum attack. |
Frequently asked questions
Is Minimum Health to Beat Game easy or hard?
The problem is rated Medium because the greedy insight is not immediately obvious. Once you recognize that armor should be applied to the largest attack, the implementation becomes straightforward and runs in linear time.
Minimum Health to Beat Game Python/Java solution
Most implementations follow the same logic: compute the total damage, track the maximum attack, then apply the formula sum(damage) - min(maxDamage, armor) + 1. The code is short and translates directly across Python, Java, C++, Go, and TypeScript.
How to solve Minimum Health to Beat Game in O(n)?
Iterate through the damage array to compute the total sum and the maximum damage value. Apply the armor to that maximum attack, reducing it by min(maxDamage, armor). Subtract that reduction from the total damage and add 1 to ensure health never reaches zero.
What is the best approach for Minimum Health to Beat Game?
The optimal approach is a greedy strategy. Compute the total damage from all attacks and apply the armor to the largest damage value because it maximizes the reduction. The minimum health required is sum(damage) - min(max(damage), armor) + 1, which runs in O(n) time and O(1) space.
Is Minimum Health to Beat Game asked at Google/Amazon/Meta?
Greedy array problems with single-use optimizations commonly appear in interviews at companies like Amazon, Google, and Meta. Variants that involve minimizing damage or maximizing a single resource usage are especially common in coding rounds.
What data structure is used in Minimum Health to Beat Game?
The problem primarily uses an array traversal. Only simple variables are required to track the running sum of damage and the maximum value, making the solution O(1) in additional space.
What is the time complexity of Minimum Health to Beat Game?
The optimal solution runs in O(n) time because you scan the damage array once to compute the total damage and track the maximum attack. Space complexity is O(1) since only a few variables are needed regardless of input size.