Minimum Health to Beat Game - Practice Coding Problems

Minimum Health to Beat Game - Problem

Array Greedy Medium

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 i-th 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.

Input & Output

Example 1 — Basic Case

$ Input: damage = [2,7,4,3], armor = 4

› Output: 10

💡 Note: Use armor on level 1 (damage 7), reducing it to 3. Total damage becomes [2,3,4,3]. Starting with 10 health: 10→8→5→1→(-2), but we need health > 0, so minimum is 10.

Example 2 — High Armor Value

$ Input: damage = [2,5,3,4], armor = 7

› Output: 10

💡 Note: Use armor on level 1 (damage 5), reducing it to 0. Total damage becomes [2,0,3,4]. Starting with 10 health: 10→8→8→5→1. Minimum health needed is 10.

Example 3 — Small Armor

$ Input: damage = [3,3,3], armor = 1

› Output: 8

💡 Note: Use armor on any level to reduce one 3 to 2. Total damage becomes [2,3,3] or similar. Starting with 8 health: 8→6→3→0, but need > 0, so minimum is 8.

Constraints

n == damage.length
1 ≤ n ≤ 10⁵
0 ≤ damage[i] ≤ 10⁶
0 ≤ armor ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of damage per level and armor value

Strategy

Choose optimal level to use armor for maximum benefit

Output

Minimum health needed to survive all levels

Key Takeaway

🎯 Key Insight: Use armor on the level with maximum damage to minimize total damage and starting health requirement

Asked in

a Amazon 15 G Google 12

The key insight is to use armor on the level with maximum damage for optimal benefit. The greedy approach works: find the level where armor provides maximum damage reduction, then simulate the game to calculate minimum starting health. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Use Armor on Maximum Damage	O(n)	O(1)	Use armor on the level with maximum damage to minimize total damage
Brute Force - Try All Armor Positions	O(n²)	O(1)	Try using armor on each level and find the minimum starting health

Greedy - Use Armor on Maximum Damage — Algorithm Steps

Step 1: Find the level with maximum damage that benefits most from armor
Step 2: Calculate total damage with armor optimally placed
Step 3: Work backwards to find minimum starting health needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Max Damage

Identify level with maximum damage that benefits from armor

Apply Armor

Use armor on that level to reduce damage

Calculate Health

Work through levels to find minimum starting health

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long solution(int* damage, int damageSize, int armor) {
    if (damageSize == 0) return 1;
    
    // Find the level where using armor gives maximum benefit
    int maxBenefit = 0;
    int bestLevel = -1;
    for (int i = 0; i < damageSize; i++) {
        int benefit = (damage[i] < armor) ? damage[i] : armor;
        if (benefit > maxBenefit) {
            maxBenefit = benefit;
            bestLevel = i;
        }
    }
    
    // Calculate minimum health needed
    long long health = 1;
    long long minHealth = 1;
    
    for (int i = 0; i < damageSize; i++) {
        long long actualDamage = damage[i];
        if (i == bestLevel) {
            actualDamage = (damage[i] - armor > 0) ? damage[i] - armor : 0;
        }
        
        health -= actualDamage;
        if (health <= 0) {
            long long needed = -health + 1;
            minHealth += needed;
            health = 1;
        }
    }
    
    return minHealth;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse damage array
    int damage[1000];
    int damageSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            damage[damageSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int armor;
    scanf("%d", &armor);
    
    printf("%lld\n", solution(damage, damageSize, armor));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find max damage, then single pass to simulate

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Use Armor on Maximum Damage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler