Skip to main content
Talentd

Minimum Health to Beat Game - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedy7 min readAsked at: Amazon
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • 0 <= damage[i] <= 105
  • 0 <= 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 DamageO(n)O(1)Optimal solution for production and interviews. One pass to compute total damage and maximum attack.

Video Solution

MINIMUM HEALTH TO BEAT GAME | LEETCODE 2214 | TOP AMAZON QUESTION | PYTHON • Cracking FAANG • 1,999 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Health to Beat Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Dungeon Game

Next

Eliminate Maximum Number of Monsters