Problem overview
The method killMonsters receives the monsters' damage values in fight order, damage, the number of magic potions K and the hero's starting health HP. Fighting a monster subtracts its damage from the hero's health, and a negative damage heals the hero instead. A potion kills one monster instantly, with no fight and no loss of health. The hero dies when health reaches zero or less. The method returns the largest number of monsters the hero can kill, assuming the potions are used as well as possible.
In the example, K = 2, HP = 10 and damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3]. Health goes 13, 11, 8, 10 over the first four monsters. Then the two 8s and the 6 would cost 22 health, but two potions can cancel the two biggest hits. The 4 brings health to exactly 0, so the hero kills 8 monsters in total and goes no further.
Approach: decide about potions afterwards
The difficulty is choosing where to spend the potions. A potion on the first big monster may be a waste if a bigger one comes later. The useful trick is to postpone the decision: fight every monster as if no potion existed, and only when health runs out look back and apply a potion to whichever monster already fought hurt the most. Applying it means giving that monster's damage back to the hero, as if the monster had been killed by the potion instead of the fight.
Taking back the largest damage so far is optimal, because it restores the most health with a single potion. To find that largest damage quickly, keep the damage of every monster fought so far in a max heap. Monsters with zero or negative damage never go in: they cost nothing, so they never need a potion.
The loop stops at the first monster the hero can't survive. The number of monsters killed is how far it got.
Swift has no heap in its standard library, so the lesson provides a MaxHeap struct with insert, extract and isEmpty.
Step by step
- Create the heap.
var kills = MaxHeap(). It is avarbecause inserting and extracting change it. - Loop with an index.
for i in 0..<damage.count. The index matters because the answer is a number of monsters. - Skip harmless monsters. If
damage[i] <= 0, add-damage[i]toHPandcontinue. Parameters in Swift are constants, so the starter code first copiesKandHPinto variables with the same names. - Fight. Subtract
damage[i]fromHP. - Remember the monster. Insert
damage[i]intokills, so a potion can still be applied to it later. - Use potions while needed. Loop while
HP <= 0 && K > 0 && !kills.isEmpty: the hero is out of health and still has a potion and a fought monster to use it on. - Apply one potion. Inside, add
kills.extract(), the largest damage, back toHPand doK -= 1. Swift has no--operator. - Fail case. After the loop, if
HP < 0, returni. Even with potions the hero can't survive monsteri, so only theimonsters before it count, since indices start at 0. - Zero health. If
HP == 0, returni + 1. Monsteriis killed, but the hero has no health left and no potion to continue with. - Survived everyone. After the
forloop, returndamage.count.
The solution in Swift
class Solution {
func killMonsters(_ damage: [Int], _ K: Int, _ HP: Int) -> Int {
var K = K
var HP = HP
var kills = MaxHeap()
for i in 0..<damage.count {
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 -= 1
}
if HP < 0 {
return i
}
if HP == 0 {
return i + 1
}
}
return damage.count
}
}
The Swift details worth a closer look:
- Shadowing a parameter.
var K = Kdeclares a new local variable with the same name as the constant parameter, initialised from it. This is the usual Swift idiom for a parameter you want to change. continue. It skips the rest of the loop body and moves to the next index.isEmptyis a property, so it is written without parentheses.- Returning from inside a loop. Both early
returnstatements end the method at once, which is why no code after the loop has to repeat the checks. - Overflow. Swift's
Intis 64 bits and an overflowing addition crashes the program, so very large damage values would need care. Ordinary values are far from the limit.
Complexity
Time: O(n log n). Every monster is inserted into the heap at most once, and every extraction removes one entry for good, so there are at most n insertions and n extractions, each O(log n).
Space: O(n). The heap can hold the damage of every monster fought.
Edge cases and common mistakes
- No monsters. The method returns 0, which equals
damage.count. - No potions. With
K = 0,[4, 4]andHP = 5, the second fight leaves health at -3, so the method returns 1. - Health of exactly zero.
[5, 1]withK = 0andHP = 5returns 1: the first monster takes the hero to 0, and that monster counts. - A potion saves the hero.
[6]withK = 1andHP = 5returns 1. - Not enough potions.
[6, 7]withK = 1andHP = 5returns 1: the potion handles the 6, and the 7 is too strong. - Healing monsters. A zero or negative damage never enters the heap. Putting a negative value in would make a "potion" take health away.
- Spending a potion at once. Using a potion on the current monster when health runs out can be wrong, because an earlier monster may have hurt more. The heap finds the biggest one.
Testing
damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3],K = 2,HP = 10gives8.damage = [],K = 1,HP = 5gives0.damage = [3, 3, 3],K = 0,HP = 7gives2.damage = [3, 3, 3],K = 1,HP = 7gives3.damage = [6, 7],K = 1,HP = 5gives1.
