Problem overview
The method killMonsters receives an array damage, a number of magic potions K and the hero's health HP. The hero fights the monsters in the given order. Fighting monster i costs damage[i] health points, and a negative value heals the hero by that amount instead. A potion kills a monster instantly, without any fight and without any damage. When HP reaches zero or below, the hero is dead. The method returns the largest number of monsters the hero can kill.
In the example, K = 2, HP = 10 and damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3]. The answer is 8. A good plan spends the two potions on the monsters with damage 8: the hero reaches 13, 11, 8 and 10 health, skips both 8s, then fights 6 and 4 and ends the eighth fight with exactly 0 HP. The ninth monster, with damage 3, can no longer be beaten.
Approach: fight first, then regret the most expensive fight
The hard part is deciding where the potions go. Trying every placement is far too many combinations. A greedy rule works better: whenever the hero would die, a potion should have gone to the monster that hurt the most so far.
That is a statement about the past, but it can be applied afterwards. Walk through the monsters, fight each one and remember its damage. If the HP drops to zero or below, pretend a potion was used on the costliest earlier fight (the current monster included): add that damage back to the HP and use up one potion. Repeat while the HP is still not positive and potions remain. This reaches the same state as spending the potions in advance on those monsters, but you only decide when the problem actually shows up.
To find the costliest fight quickly you need a structure that always gives the maximum and lets you add new values: a max heap. The lesson provides a MaxHeap class with insert, extract and isEmpty, since TypeScript has no heap built in.
Healing monsters (damage zero or less) are special. They never cost anything, so they never need a potion and never go into the heap. The hero just gains the HP.
Step by step
- Create the heap and store it in a
constnamedkills. It remembers the damage of every monster fought so far. - Loop over the monsters with an index
i, because the answer is a count. - Handle healing monsters. When
damage[i] <= 0, add-damage[i]toHPandcontinue. Adding the negated value is how a negative damage raises the health. - Fight the monster: subtract
damage[i]fromHP. - Remember it: insert
damage[i]into the heap, so a potion can still be assigned to this fight later. - Repair the health with potions. A
whileloop runs whileHP <= 0, a potion remains (K > 0) and the heap isn't empty. - Use one potion. Extract the largest damage, add it back to
HPand decrementK. - Dead after the potions: if
HP < 0, returni. Monsterican't be survived, so only theimonsters before it (indexes 0 toi - 1) count. - Exactly zero: if
HP === 0, returni + 1. Monsteriis killed, but the hero has no health left, so the fights stop there. The loop only ends at exactly 0 when no potion or no fought monster remains. - Survived everything: after the loop, return
damage.length.
The solution in TypeScript
class Solution {
killMonsters(damage: number[], K: number, HP: number): number {
const kills = new MaxHeap();
for (let i = 0; i < damage.length; i++) {
if (damage[i] <= 0) {
HP += -damage[i];
continue;
}
HP -= damage[i];
kills.insert(damage[i]);
while (HP <= 0 && K > 0 && !kills.isEmpty()) {
HP += kills.extract();
K--;
}
if (HP < 0) {
return i;
}
if (HP === 0) {
return i + 1;
}
}
return damage.length;
}
}
The TypeScript details worth a closer look:
- Parameters are ordinary variables.
HPandKare numbers, which are passed by value, so changing them inside the method doesn't affect the caller's variables. That is why the solution can use them as counters. - The parameter order. The signature is
(damage, K, HP), so a call looks likekillMonsters([4, 9], 0, 5): the potions come before the health. continueskips to the next iteration. The healing branch uses it so the fight code below only runs for real damage.- Types vanish after compiling. The annotations on
damage,KandHPcheck calls when the code is compiled, but they don't convert or validate anything while the program runs.
Complexity
Time: O(n log n). Each monster is inserted into the heap at most once and extracted at most once, because a potion removes it from the heap for good. Each heap operation costs O(log n) on a heap of at most n values, and the potion loop never runs more than K times in total.
Space: O(n). The heap can hold the damage of every monster that was fought and not yet cured with a potion.
Edge cases and common mistakes
- No potions. With
K = 0the potion loop never runs. Fordamage = [5, 5]andHP = 10, the HP reaches exactly 0 on the second monster, and the method returns 2. - A monster that is too strong. A monster with
damage[i] >= HPcan't be fought without a potion, apart from the case where the fight ends at exactly 0 HP shown above.damage = [4, 9]withK = 0andHP = 5returns 1: the first monster leaves 1 HP, and the second takes it below zero. - A potion on the current monster. Because the current damage is inserted before the potion loop, the heap's maximum may be that monster itself.
damage = [3],K = 1,HP = 3returns 1, since the potion cancels the fight. - Healing monsters in the heap. Inserting zero or negative damage would waste a potion on a monster that cost nothing, so the early
continuematters. - Spending a potion on the wrong monster. Using it on the most recent or the first fight can refund too little health. The heap makes sure each potion refunds the most.
- Returning
iwhen the HP is zero. That would miss the monster that was just killed. The two exits differ by one on purpose.
Testing
damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3],K = 2,HP = 10gives8.damage = [5, 5],K = 0,HP = 10gives2.damage = [4, 9],K = 0,HP = 5gives1.damage = [3],K = 1,HP = 3gives1.