Problem overview
A hero starts with hp health points and k magic potions, and faces the monsters in the order given by the slice damage. Fighting monster i costs damage[i] health points. A negative value heals the hero by that amount instead. A potion kills one monster outright, with no fight and no health lost. The hero dies when health reaches zero or below. The function killMonsters returns the maximum number of monsters the hero can kill, playing optimally.
A monster that takes the hero to exactly 0 health still counts as killed, but the run ends there.
In the example, k = 2, hp = 10 and damage = []int{-3, 2, 3, -2, 8, 8, 6, 4, 3, 3}. The answer is 8. The hero fights the first four monsters, ending at 10 health. Then the two potions go to the two monsters with damage 8, and the hero fights the monsters with damage 6 and 4, reaching 4 and then 0 health. The ninth monster would be one too many.
Approach: fight first, spend potions in hindsight
Deciding where to use potions in advance is hard: a potion is worth the most on a monster with large damage, but you don't know yet which monsters are large. Trying every choice of k monsters would take exponential time.
The trick is to postpone the choice. Fight every monster as if no potion existed, and keep the damage of each fought monster in a max heap. When health drops to zero or below, look back for the fight that cost the most: popping the largest damage from the heap and adding it back to the health is the same as having used a potion on that monster in the first place. Each potion spent this way restores as much health as any single potion can.
Monsters with non-positive damage never need a potion, since they only help. They are applied directly and never enter the heap.
After each monster, there are three outcomes:
- health is positive: the hero survives and continues;
- health is exactly 0 after potions are exhausted: this monster is killed, and the run ends with
i + 1kills; - health is negative even after every possible potion: the hero loses to monster
i, so only theimonsters before it were killed.
Here is the trace for the example (potions left in brackets):
- Monsters 0 to 3: health goes 13, 11, 8, 10.
- Monster 4 (damage 8): health 2.
- Monster 5 (damage 8): health -6. The heap's largest damage is 8, so a potion cancels it and health returns to 2 (1 left).
- Monster 6 (damage 6): health -4. A potion cancels the other 8, and health becomes 4 (0 left).
- Monster 7 (damage 4): health 0, and no potions remain, so the function returns 8.
Step by step
- Create an empty max heap with
&maxHeap{}and store it inkills. ThemaxHeaptype is provided by the lesson. It remembers the damage of every fought monster, so the largest can be undone later. The heap is used through a pointer becausecontainer/heapneeds one. - Loop over
damagewithfor ... range, taking both the indexiand the elementvalue. The index matters because the answer is a count of monsters. - Handle healing monsters. Copy
valueintocurrentDamage. If it is 0 or negative, add-currentDamagetohpandcontinue. Such a monster never needs a potion and never enters the heap. - Fight the monster by subtracting
currentDamagefromhp. - Remember the fight by pushing
currentDamagewithheap.Push, the package function that keeps the heap ordered. - Spend potions while needed with a condition-only
for: whilehp <= 0 && k > 0 && kills.Len() > 0, meaning health is gone, a potion is left, and a fought monster exists. - Undo the worst fight. Pop the largest damage with
heap.Pop(kills), assert it toint, add it tohp, and decrementk. - Health below zero: if
hp < 0, returni. Even with all potions the hero loses to monsteri, and indices start at 0, soiis the number of monsters before it. - Health exactly zero: if
hp == 0, returni + 1. This monster is killed, but nothing more can follow. The potion loop stops at exactly 0 only when no potion or no fought monster remains. - Return
len(damage)after the loop, because the hero survived every monster.
The solution in Go
The solution uses the lesson's maxHeap type with the container/heap package. A typical definition of that type is:
type maxHeap []int
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *maxHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
And the function:
func killMonsters(damage []int, k, hp int) int {
kills := &maxHeap{}
for i, value := range damage {
currentDamage := value
if currentDamage <= 0 {
hp += -currentDamage
continue
}
hp -= currentDamage
heap.Push(kills, currentDamage)
for hp <= 0 && k > 0 && kills.Len() > 0 {
hp += heap.Pop(kills).(int)
k--
}
if hp < 0 {
return i
}
if hp == 0 {
return i + 1
}
}
return len(damage)
}
The Go details worth knowing:
- Parameters are copies.
kandhpare ordinaryintparameters, so the function changes its own copies without affecting the caller. The signaturek, hp intgives both the typeint. rangegives index and value.for i, value := range damagecopies each element intovalue. Use_instead of a name when you don't need one of them.&maxHeap{}is a pointer to an empty heap. The methodsPushandPopneed to change the slice's length, soheap.Push(kills, ...)takes the pointer.- Type assertion.
heap.Pop(kills)returns anany. Writing.(int)extracts theintso it can be added tohp. Without it, the code doesn't compile. - Condition-only
for. Go's while loop is aforwith just a condition. Here three conditions are joined with&&. continuein arangeloop jumps to the next element, so healing monsters skip the fight logic below.
Complexity
Let n be the number of monsters.
Time: O(n log n). Each monster causes one push, O(log n). Each potion causes one pop, O(log n), and at most min(k, n) pops happen in the whole run.
Space: O(n). The heap can hold the damage of every fought monster. When k is small, a heap capped at k entries would use less memory, but the lesson's version keeps them all.
Edge cases and common mistakes
- No monsters. An empty slice returns 0, since the loop never runs and
len(damage)is 0. - Exactly zero health.
damage = []int{5},k = 0,hp = 5returns 1: the monster is killed and the hero reaches 0. Withhp = 6the result is also 1. - A potion rescues the fight. With
damage = []int{5},k = 1,hp = 5, the potion cancels the only fight, health returns to 5 and the result is 1. - Losing to the fourth monster.
damage = []int{3, 3, 3, 3},k = 0,hp = 10returns 3: after three fights health is 1, and the fourth takes it to -2, so only three monsters were killed. - Healing monsters first.
damage = []int{-5, 9, 1},k = 0,hp = 5returns 3: health goes 10, 1, 0, and the third monster is killed at exactly 0. - Returning
i + 1on a negative result. That would count the monster that killed the hero, when only a monster killed at exactly 0 health counts. - Using the potion on the current monster only. A potion can be better spent on an earlier, larger fight. In the example, the second potion goes to a monster two steps back.
- Putting healing monsters in the heap. A potion on a monster that heals the hero would lose health. They stay out of the heap on purpose.
- Using a min heap. It would cancel the smallest fight, which restores the least health.
Testing
damage = []int{-3, 2, 3, -2, 8, 8, 6, 4, 3, 3},k = 2,hp = 10gives 8.damage = []int{5},k = 0,hp = 5gives 1.damage = []int{3, 3, 3, 3},k = 0,hp = 10gives 3.damage = []int{-5, 9, 1},k = 0,hp = 5gives 3.damage = []int{},k = 1,hp = 5gives 0.