Problem overview
The function kill_monsters receives damage, a vector with the damage of each monster in the order you meet them, the number of magic potions k, and your starting health hp. Note the order of the parameters: the vector first, then k, then hp.
Fighting a monster subtracts its damage from your health. A negative damage heals you by that amount. A potion kills a monster outright, with no loss of health. You fight the monsters in order, and the function returns how many of them you can kill when you play the best way.
In the example, damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3], k = 2 and hp = 10, and the answer is 8.
Approach: spend the potions after the fact, on the worst hits
The hard part looks like a choice: which monsters should get a potion? Deciding in advance means guessing about the future. The trick is to decide late. Fight every monster, and when the health would run out, imagine that a potion had been used earlier on the monster that hurt the most so far. That gives back exactly that monster's damage.
This is a greedy choice, and it is safe: if you must use k potions among the monsters you have faced, the most health you can save is by using them on the largest damages among them. So the program needs the largest damage seen so far, many times, with new values arriving all the time. A max-heap does that. Rust's BinaryHeap is a max-heap by default.
Monsters with damage 0 or below only heal you. They never need a potion, so they never enter the heap.
Take the example. Health goes 10, 13, 11, 8, 10 through the first four monsters. The 8 at index 4 brings it to 2, and the next 8 to -6. The heap holds 2, 3, 8 and 8, so a potion on one 8 brings health back to 2, and the first potion is spent. The 6 at index 6 brings it to -4, and the second potion cancels the other 8 and brings health to 4, and no potions remain. The 4 at index 7 takes health to exactly 0, which ends the run: 8 monsters, indices 0 to 7.
Step by step
- Create the heap
kills, a mutableBinaryHeap<i32>made withBinaryHeap::new(). It remembers the damage of every monster fought, so the largest can be undone with a potion. - Loop over the indices
iin0..damage.len(). The index matters, because the answer is a count of monsters. - Handle healing monsters. If
damage[i] <= 0, add-damage[i]tohpandcontinueto the next monster. - Fight the monster. Subtract
damage[i]fromhp. - Remember the damage. Push
damage[i]ontokills, so a potion can still be used on this monster later. The current monster can itself be the largest, and then it is the one to use the potion on. - Use potions while needed. A
whileloop runs as long ashp <= 0, a potion remains (k > 0) and the heap is not empty. - Undo the worst fight. Inside the loop, pop the largest damage with
kills.pop().unwrap(), add it back tohp, and decreasek. Theunwrapis safe because the loop condition checked that the heap is not empty. - Stop when health is negative. If
hp < 0after the potions, returni as i32. Monsterican't be survived, and the monsters before it,iof them since indices start at 0, were killed. - Stop when health is exactly zero. If
hp == 0, return(i + 1) as i32. The loop above ends at zero only when no potions are left, and the run ends at this monster, which is counted. - Survived everyone. After the
forloop, returndamage.len() as i32, as the final expression with no semicolon.
The solution in Rust
use std::collections::BinaryHeap;
impl Solution {
fn kill_monsters(damage: Vec<i32>, mut k: i32, mut hp: i32) -> i32 {
let mut kills: BinaryHeap<i32> = BinaryHeap::new();
for i in 0..damage.len() {
if damage[i] <= 0 {
hp += -damage[i];
continue;
}
hp -= damage[i];
kills.push(damage[i]);
while hp <= 0 && k > 0 && !kills.is_empty() {
hp += kills.pop().unwrap();
k -= 1;
}
if hp < 0 {
return i as i32;
}
if hp == 0 {
return (i + 1) as i32;
}
}
damage.len() as i32
}
}
The Rust details worth a closer look:
muton parameters.mut k: i32andmut hp: i32make the parameters mutable local variables. The function changes its own copies, and the caller's numbers are not touched.continueand earlyreturn.continueskips the rest of the loop body for this monster.returnleaves the function from inside the loop. The last line, with no semicolon, is the result when the loop completes.usizetoi32. The loop index andlen()areusize, but the function returnsi32, so the results are cast withas i32. The parentheses in(i + 1) as i32make the addition happen before the cast.pop()returns anOption. The callkills.pop().unwrap()would panic on an empty heap. The!kills.is_empty()test in the loop condition rules that out, and the condition stops evaluating at the first false part.- Heap contents. Only monsters that were fought and hurt you are in the heap. A potion used on one acts as if it had been used when the monster first appeared, and its damage is added back.
Complexity
Time: O(n log n). Each monster is pushed at most once, and popped at most once, because a popped damage is gone. Each push and pop takes O(log n). The while loop also stops after at most k iterations in total.
Space: O(n). The heap can hold the damage of every monster fought, which is up to n values.
Edge cases and common mistakes
- No monsters. The loop does not run and the function returns 0.
- No potions. With
k = 0on the example, health goes 10, 13, 11, 8, 10, 2, -6, and the function returns 5, the number of monsters before the second 8 at index 5. - Healing monsters. A monster with damage 0 or below only raises health. It needs no potion and is never pushed onto the heap.
- Potions on the current monster. The monster is pushed before the potion loop, so when it is the largest damage so far, the potion goes to it.
- Health exactly zero. With
[5, 5, 1],k = 0,hp = 10, the second monster takes health to exactly 0, and the function returns 2. The run ends there, so the third monster is not fought. - Zero also ends the run before later healers. With
[4, -5, 1],k = 0,hp = 4, the function returns 1, although the second monster would have healed you. - Using up the potions too early. Spending a potion on every monster at first would waste them on small damages. Waiting until health runs out, and then choosing the largest damage so far, avoids that.
- Returning
i + 1for a negative health. The monster that can't be survived is not counted, so the answer isi.
Testing
damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3],k = 2,hp = 10gives8.- The same
damagewithk = 0gives5. - The same
damagewithk = 5gives10. damage = [20, 1],k = 1,hp = 10gives2.damage = [3, 9, 2],k = 1,hp = 5gives3.damage = [],k = 2,hp = 10gives0.
