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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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:

1
2
3
4
5
6
7
8
9
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.

Solution

Method 1 – Greedy: Maximize Armor Usage

Intuition

To minimize the starting health, use the armor on the level with the highest damage, since armor can only be used once and blocks up to armor damage. Subtract the minimum of the largest damage and armor from the total damage to get the minimum health needed (plus 1, since health must always be > 0).

Approach

  1. Calculate the total sum of all damages.
  2. Find the maximum value in the damage array.
  3. The best use of armor is on the level with the highest damage, reducing the total damage by min(max_damage, armor).
  4. The minimum starting health is total_damage - min(max_damage, armor) + 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
  long long minimumHealth(vector<int>& dmg, int armor) {
    long long sum = 0;
    int mx = 0;
    for (int d : dmg) {
      sum += d;
      mx = max(mx, d);
    }
    long long ans = sum - min(mx, armor) + 1;
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func minimumHealth(dmg []int, armor int) int64 {
  sum, mx := 0, 0
  for _, d := range dmg {
    sum += d
    if d > mx {
      mx = d
    }
  }
  ans := int64(sum - min(mx, armor) + 1)
  return ans
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public long minimumHealth(int[] dmg, int armor) {
    long sum = 0;
    int mx = 0;
    for (int d : dmg) {
      sum += d;
      mx = Math.max(mx, d);
    }
    long ans = sum - Math.min(mx, armor) + 1;
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  fun minimumHealth(dmg: IntArray, armor: Int): Long {
    var sum = 0L
    var mx = 0
    for (d in dmg) {
      sum += d
      mx = maxOf(mx, d)
    }
    val ans = sum - minOf(mx, armor) + 1
    return ans
  }
}
1
2
3
4
5
6
class Solution:
  def minimumHealth(self, dmg: list[int], armor: int) -> int:
    total = sum(dmg)
    mx = max(dmg)
    ans = total - min(mx, armor) + 1
    return ans
1
2
3
4
5
6
7
8
impl Solution {
  pub fn minimum_health(dmg: Vec<i32>, armor: i32) -> i64 {
    let sum: i64 = dmg.iter().map(|&x| x as i64).sum();
    let mx = *dmg.iter().max().unwrap();
    let ans = sum - (mx.min(armor) as i64) + 1;
    ans
  }
}

Complexity

  • Time: O(n), where n is the number of levels (length of damage array).
  • Space: O(1), only a few variables are used.