Problem overview
A hero starts with HP health points and K magic potions and fights monsters in the given order. The array damage holds the damage each monster deals. A negative value means the monster heals you by that amount. A potion kills a monster outright, so the hero loses nothing from it. The function returns the largest number of monsters the hero can kill, with the potions used as well as possible.
For K = 2, HP = 10 and damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3] the answer is 8. The hero can reach 0 HP exactly after the eighth monster, for example by using the two potions on the two monsters that deal 8 damage. The ninth monster is out of reach, so the count is 8.
Approach
You don't know in advance which monsters deserve a potion. The trick is to decide late:
- Fight each monster as if no potion existed and subtract its damage from HP.
- Remember every damage in a max heap, so the biggest hit so far is always on top.
- If HP drops to 0 or below, you go back in time: use a potion on the monster that hurt you most, which gives its damage back.
Spending a potion on the biggest hit among the monsters fought so far is the best use of it, because it restores the most HP. If even that does not bring HP above 0, then no choice of potions would, and the hero cannot kill this monster. Monsters that heal the hero never need a potion and never go into the heap.
Each monster enters and leaves the heap at most once, so the cost is O(n log n).
Step by step
- The heap.
killsis aPriorityQueue<Int>built withcompareByDescending { it }. The queue is a min heap by default, and the comparator reverses it so that the largest damage is on top. - The loop. A
forloop overdamage.indicesgives the indexi. The index is needed because the answer counts monsters. - Healing monsters. If
damage[i] <= 0, add-damage[i]tohpandcontinue. The code copies the parameters intovar k = Kandvar hp = HP, because Kotlin function parameters are read-only. - Fight. Subtract
damage[i]fromhp. - Remember the hit. Add
damage[i]tokills, so a potion can still be used on this monster later. - Use potions while needed. The
whileloop runs as long ashp <= 0, a potion is left (k > 0) and the heap is not empty. - One potion. Inside the loop,
kills.poll()removes the largest damage so far, that damage is added back tohp, andk--uses up the potion. - Dead. After the
while, ifhp < 0, returni: the hero can't survive monsteri, so only theimonsters before it count. - Zero HP. If
hp == 0, returni + 1. Monsteriis killed, but the hero has no HP left, so the fight stops there. The potion loop ends at exactly 0 only when no potion or no earlier monster is left to use. - Survived. After the loop, return
damage.size.
The solution in Kotlin
class Solution {
fun killMonsters(damage: IntArray, K: Int, HP: Int): Int {
var k = K
var hp = HP
val kills = PriorityQueue<Int>(compareByDescending { it })
for (i in damage.indices) {
if (damage[i] <= 0) {
hp += -damage[i]
continue
}
hp -= damage[i]
kills.add(damage[i])
while (hp <= 0 && k > 0 && kills.isNotEmpty()) {
hp += kills.poll()
k--
}
if (hp < 0) {
return i
}
if (hp == 0) {
return i + 1
}
}
return damage.size
}
}
Kotlin details worth knowing:
- Parameters are
vals and can't be reassigned. That's why the code copiesKandHPinto thevarskandhp. Assigning toKwould not compile. PriorityQueuecomes fromjava.util; a standalone file needsimport java.util.PriorityQueue.kills.poll()returns a platform type, sohp += kills.poll()compiles. TheisNotEmpty()check in the loop condition guarantees that the queue has a value to give.&&short-circuits, so the conditions are checked left to right and stop at the first false one.continueskips the rest of that pass of theforloop, like in Java.
Following the example
Start with hp = 10. The first monster (-3) heals, so HP is 13. Monsters with damage 2 and 3 bring it to 8, and the monster with -2 heals it to 10. The 8 brings it to 2 and the next 8 to -6. The potion loop pops the 8, giving HP 2 and one potion left. Then comes 6: HP -4. The loop pops the other 8, giving HP 4 and no potions left. Monster 7 (damage 4) brings HP to 0, so the function returns i + 1, which is 8.
Complexity
Time: O(n log n). Every monster with positive damage is added to the heap once, and each is polled at most once. Both operations cost O(log n). Because each potion removes one heap entry, the inner loop runs at most K times in total.
Space: O(n) for the heap in the worst case.
Edge cases and common mistakes
- No potions. With
K = 0the heap is never polled, and the hero dies at the first monster that brings HP to 0 or below. - Monsters that heal. A damage of 0 or less raises HP and is skipped by the heap. A potion on a healing monster would waste it.
- Dying at exactly 0. The hero reaching 0 HP is dead, but the monster that did it still counts as killed. That is why the code returns
i + 1here andiwhen HP is negative. - Using a min heap. That would spend potions on the smallest hit and recover the least HP.
- Using the original parameters. Updating
HPin place doesn't compile in Kotlin, and changingkandhpinside the loop is what the algorithm needs.