Start learning free

LESSON 313 OF 409 · HEAP

Kill Monsters in C++: Greedy with a Max-Heap (priority_queue)

Practice O(n log n) Read the full explanation

You are a hero in a game, initially having HP health points and K magic potions.

You have to fight N monsters in the order they are given, knowing the damage each monster deals to you.

damage[i] represents the damage the monster deals to you when you fight them. If the damage is negative, it means your HP increases by that amount.

If you use a magic potion on a monster, it will kill the monster without you fighting or losing health points.

If your HP drops below zero, you lose the fight. If it drops to exactly zero HP, you still kill that monster, but you are left with no health, so the fight ends there. Therefore you can't win against a monster that has damage[i] > HP.

Find the maximum number of monsters you can kill, considering you are playing optimally.

Example

Input: K = 2, HP = 10,
       damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3]
Output: 8
Explanation: You kill the first 8 monsters by using the two potions on the 5th and 6th monsters
STEP 1 OF 10
    Ctrl + Enter to check

    C++ · HEAP

    Kill Monsters in C++, explained

    Problem overview

    A hero starts with HP health points and K magic potions. The method killMonsters receives a vector<int> called damage, K and HP. The hero fights the monsters in the given order. Monster i takes damage[i] health points away, and a negative value gives health back instead. A potion kills one monster without a fight, so that monster costs nothing. The method returns the largest number of monsters the hero can kill in a row.

    Take K = 2, HP = 10 and damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3]. The answer is 8. With potions on the two monsters that deal 8, the hero's HP goes 13, 11, 8, 10, then stays at 10 over both skipped monsters, then 4 after the monster that deals 6, and finally 0 after the one that deals 4. Reaching exactly 0 still counts the last monster as killed, but the hero cannot fight on, so the count stops at 8.

    Approach: spend a potion only when you are forced to

    The question is where to use the potions. The brute-force answer tries every way of choosing K monsters out of N, which is far too slow. A greedy rule is enough.

    Using a potion on a monster is the same as never taking its damage. So walk through the monsters in order and fight each one. If HP drops to 0 or below, the hero would have died, which means a potion was needed somewhere among the monsters fought so far. The best place for it is the monster that hurt the most, because cancelling the largest damage gives back the most HP. Doing it afterwards is allowed: if the potion had been used on that monster at the time, every HP value in between would only have been higher, so the hero would have been safe in the meantime too.

    That rule needs a way to find the largest damage among the monsters fought so far, again and again, while new monsters are added. That is exactly what a max-heap is for. In C++ the priority_queue<int> is a max-heap by default: top() returns the biggest element, push() adds one and pop() removes the biggest, each in logarithmic time.

    Monsters with damage 0 or less never need a potion, because they cost nothing or even help. They are applied to HP directly and never go into the heap.

    The example, step by step

    MonsterdamageHP after the fightPotionHP and K after
    0-313-13, K = 2
    1211-11, K = 2
    238-8, K = 2
    3-210-10, K = 2
    482-2, K = 2
    58-6on a monster with 82, K = 1
    66-4on a monster with 84, K = 0
    740none left0, K = 0

    At monster 7 the hero has exactly 0 HP and no potions, so the method returns 8, the number of monsters up to and including monster 7.

    Step by step

    1. Create the max-heap kills, an empty priority_queue<int>. It remembers the damage of every monster that was fought.
    2. Loop over the monsters with an int index i. The index is needed because the answer is a count of monsters.
    3. Handle healing monsters. If damage[i] <= 0, add -damage[i] to HP and continue. Subtracting a negative damage would raise HP too, but writing it as an addition makes the intent clear.
    4. Fight the monster. Subtract damage[i] from HP and push damage[i] into the heap, so a potion can still be applied to this monster later.
    5. Rescue the hero with potions. While HP <= 0 && K > 0 && !kills.empty(), take the largest damage with kills.top(), add it back to HP, remove it with kills.pop() and decrement K. The order matters, because pop() returns nothing in C++, so the value has to be read before.
    6. Decide whether the hero survived. If HP < 0 even after the potions, monster i cannot be beaten, so the hero killed the i monsters before it. Return i.
    7. Handle exactly zero. The potion loop only stops at HP == 0 when no potion is left. The hero killed monster i, but has no health left, so return i + 1.
    8. Return damage.size() after the loop: the hero survived every monster.

    The solution in C++

    class Solution {
public:
    int killMonsters(vector<int>& damage, int K, int HP) {
        priority_queue<int> kills;
        for (int i = 0; i < damage.size(); i++) {
            if (damage[i] <= 0) {
                HP += -damage[i];
                continue;
            }
            HP -= damage[i];
            kills.push(damage[i]);
            while (HP <= 0 && K > 0 && !kills.empty()) {
                HP += kills.top();
                kills.pop();
                K--;
            }
            if (HP < 0) {
                return i;
            }
            if (HP == 0) {
                return i + 1;
            }
        }
        return damage.size();
    }
};

    The C++ details worth a closer look:

    • Parameters by value and by reference. damage is a reference, so the vector is not copied. K and HP are plain int parameters, copies local to the call. That is why the method can freely decrement K and change HP without affecting the caller.
    • The heap is a max-heap by default. A min-heap would need priority_queue<int, vector<int>, greater<int>>. Here the biggest damage is wanted, so the default is right.
    • top() before pop(). top() returns a reference to the largest element, and pop() returns void. Calling top() on an empty queue is undefined behaviour, which is what the !kills.empty() check in the loop condition prevents.
    • damage.size() is unsigned. i < damage.size() compares an int with a size_t, which is fine here because i starts at 0. The final return damage.size() converts back to int implicitly.
    • Overflow. HP and the damage values are plain int. If the inputs could be large enough for the running total to pass about two billion, signed overflow would be undefined behaviour, and long long would be the safer type.

    Complexity

    Time: O(N log N), where N is the number of monsters. Each monster is pushed at most once and popped at most once, and each heap operation costs O(log N), since the heap can hold up to N damages. The potion loop runs at most K times in total, never more than N.

    Space: O(N), for the heap that may hold the damage of every fought monster.

    Edge cases and common mistakes

    • No monsters. The loop does not run and the method returns 0.
    • No potions. With K = 0 the hero fights until HP runs out. For damage = [3, 3, 3], HP 10 gives 3, and HP 9 also gives 3, because ending at exactly 0 counts the last monster. With damage = [5], HP 4 gives 0.
    • Healing monsters. They must not go into the heap. A potion spent on a healing monster would only cancel the health it gives.
    • Zero damage. A monster with damage 0 is treated as a healing monster that heals nothing, and the code skips it correctly.
    • Using potions too early. Spending a potion on the first big monster you meet is not optimal. The potion should go to the largest damage seen so far, and only when HP requires it.
    • Returning i instead of i + 1. The two returns differ on purpose: negative HP means monster i was not killed, while exactly 0 means it was.
    • Reading top() after pop(). The element is gone by then, and you would add the wrong damage back.

    Testing

    • damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3], K = 2, HP = 10 gives 8.
    • damage = [], K = 1, HP = 5 gives 0.
    • damage = [5], K = 0, HP = 6 gives 1, and with HP = 4 gives 0.
    • damage = [3, 3, 3], K = 1, HP = 5 gives 2.
    • damage = [5], K = 1, HP = 3 gives 1.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free