Minimum Health to Beat Game - Solution & Explanation

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.