← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
Practice/Amazon/Leetcode 2214. Minimum Health to Beat Game
CodingMust
You are playing a dungeon quest game where you must traverse through a series of rooms sequentially. Each room contains an enemy that deals a specific amount of damage to your health when you enter. You have a special armor shield that can absorb damage, but it can only be used once in one room of your choice to completely block the damage from that room.
Your health must remain strictly positive (at least 1) throughout the entire journey, including after clearing all rooms. Determine the minimum starting health required to successfully complete the dungeon.
1 <= damage.length <= 10^51 <= damage[i] <= 10^60 <= armor <= 10^6Example 1:
``
Example 1:
Input: damage = [2, 5, 3], armor = 4 Output: 7 Explanation: Total damage without armor is 2 + 5 + 3 = 10. Use armor on the room with 5 damage. Since armor value is 4, it blocks 4 damage from that room. Actual damage taken: 2 + (5-4) + 3 = 6 Minimum starting health needed: 6 + 1 = 7
Example 2:
Input: damage = [3, 3, 3], armor = 0 Output: 10 Explanation: No armor to use. Total damage is 9. Minimum starting health: 9 + 1 = 10
Example 3:
Input: damage = [1, 2, 3, 4, 5], armor = 10 Output: 11 Explanation: Total damage is 15. Use armor on the room with 5 damage. Since armor value (10) exceeds the damage (5), it completely blocks that room. Actual damage taken: 1 + 2 + 3 + 4 + 0 = 10 Minimum starting health: 10 + 1 = 11
Input: damage = [2, 5, 3], armor = 4
Output: 11
Explanation: Total damage without armor is 10. Best strategy is to use armor on the room with 5 damage (since armor only blocks up to 4 damage in any case, we want to use it on a room dealing >= 4 damage). Net damage: 2 + (5-4) + 3 = 6. Minimum starting health is 7... wait, let's recalculate: if we use armor on the 5-damage room and it blocks 4 damage, we take 2 + 1 + 3 = 6 damage total, needing 7 starting health. Actually, if armor fully blocks one room: 2 + 0 + 3 = 5 damage (blocking the 5-damage room completely if armor >= 5, but armor is only 4). We take 2 + (5-4) + 3 = 6 damage if we use armor on room 2. Or we could skip: 2 + 5 + 3 = 10 without armor. Best is to use armor on the highest damage room where it helps most. Total damage = 10, armor reduces by min(4, max(damage)) = 4, so 10 - 4 = 6 damage taken, need 7 health. But we must end with at least 1, so 6 + 1 = 7.
Wait, let me reconsider the problem: armor blocks damage from ONE room completely up to the armor value.
Total damage = 2 + 5 + 3 = 10
If we use armor (value 4) on room with 5 damage, it blocks 4 damage from that room.
Net damage = 2 + (5-4) + 3 = 6
We need 6 + 1 = 7 starting health.
Hmm, but output says 11. Let me reread... Perhaps armor works differently. Let me assume armor provides a shield that absorbs damage cumulatively across rooms until depleted. Then: damage taken = max(0, 10 - 4) = 6, need 7 health... Still not 11.
Let me reinterpret: perhaps we can't use armor strategically, and it just provides 4 absorption total? Then 10 - 4 = 6 damage, need 7 health. Output 11 doesn't match.
Let me try: maybe the problem is we need to survive each intermediate state? Let's trace through:
- Start with health H
- After room 1 (damage 2): health = H - 2 (must be >= 1)
- After room 2 (damage 5): health = H - 2 - 5 = H - 7 (must be >= 1)
- After room 3 (damage 3): health = H - 10 (must be >= 1)
So H >= 11.
But if we use armor on room 2: H - 2 - max(0, 5-4) - 3 = H - 6, so H >= 7.
Let me rewrite with this understanding: