Start learning free

LESSON 293 OF 347 · HEAP

Kill Monsters in C#: Greedy Potions with a Max Heap

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 you reach zero HP, you die. Therefore you can't win agains 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 6^th and 7^th monsters

STEP 1 OF 10

Guided

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 an array damage, one entry per monster, and the hero fights the monsters in the given order. A positive damage[i] is subtracted from the hero's health. A negative or zero value heals the hero by that amount instead. A potion defeats a monster without any fight, so that monster deals no damage. The hero dies at zero health, and the method returns the maximum number of monsters the hero can kill.

In the example, K = 2, HP = 10 and damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3]. The answer is 8: the hero defeats the first eight monsters and cannot survive the ninth. In the best play, the two potions go to the two monsters with damage 8, the biggest ones met so far.

Approach: spend potions late, on the biggest hits

The hard part is deciding where to use the potions. Deciding at the moment each monster appears is guesswork, because a bigger monster might come later. The better idea is to postpone the decision.

Fight every monster as if no potions existed, and remember the damage of each monster fought. Only when health reaches zero or below does a potion become necessary. At that point, we may as well use it on the monster that hurt the most so far. Using a potion retroactively on that monster gives back its damage, which is the largest refund available. The hero keeps going as long as potions keep health above zero.

The remembered damages need a structure that gives back the largest one on demand, and that is a max heap. Insertion and removal cost O(log n), so the whole simulation is O(n log n).

Healing monsters (damage zero or below) never need a potion: they cannot hurt, so they never enter the heap.

Here is the example. Health goes 10, 13 (heal 3), 11, 8, 10 (heal 2), then the first 8 brings it to 2. The second 8 brings it to -6, which needs a potion: the heap's largest entry is 8, so health returns to 2 and one potion is left. The monster with damage 6 brings health to -4, so the next potion refunds an 8, and health is 4 with no potions left. The monster with damage 4 brings it to exactly 0. No potions remain, so the hero cannot continue, and the monster at index 7 is the last one killed. The answer is 8.

Step by step

Create the max heap kills as a PriorityQueue<int, int>. C#'s priority queue gives back the smallest priority first, so a comparer (x, y) => y - x reverses the order. Each damage is both element and priority.
Loop over the monsters with an index i. The index matters because the answer is a count of monsters.
Skip healing monsters. When damage[i] <= 0, add -damage[i] to HP and continue.
Fight the monster. Subtract damage[i] from HP.
Remember the fight. Enqueue damage[i] into kills, so a potion can be applied to this monster later.
Rescue the hero while needed. Run a while loop as long as HP <= 0, a potion is left (K > 0) and the heap is not empty.
Use a potion. Remove the largest damage with Dequeue(), add it back to HP, and decrement K.
Detect death. If HP < 0 after the potions, monster i cannot be beaten, and only the i monsters before it were killed.
Detect exactly zero. If HP == 0, monster i was killed but the hero has no health left, so the fight ends with i + 1 kills.
Survive everything. After the loop, return damage.Length.

The solution in C#

class Solution {
    public int KillMonsters(int[] damage, int K, int HP) {
        PriorityQueue<int, int> kills = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y - x));
        for (int i = 0; i < damage.Length; i++) {
            if (damage[i] <= 0) {
                HP += -damage[i];
                continue;
            }
            HP -= damage[i];
            kills.Enqueue(damage[i], damage[i]);
            while (HP <= 0 && K > 0 && kills.Count > 0) {
                HP += kills.Dequeue();
                K--;
            }
            if (HP < 0) {
                return i;
            }
            if (HP == 0) {
                return i + 1;
            }
        }
        return damage.Length;
    }
}

Some C# details to notice:

Parameters are local copies. K and HP are int values, so the method may change them freely. The caller's variables stay as they were.
Element and priority. Enqueue(element, priority) takes two arguments, and Dequeue() returns the element. With the damage used for both, HP += kills.Dequeue() adds the damage back directly.
The reversing comparer. Comparer<int>.Create builds a comparer from a lambda, and y - x makes larger priorities come out first. The subtraction could overflow for values near the limits of int, where y.CompareTo(x) is the safe form. The damages in this lesson are small.
continue. It jumps straight to the next iteration, skipping the fight code below it.
Count is a property, so kills.Count has no parentheses. Calling Dequeue() on an empty queue throws, which is why the loop condition checks kills.Count > 0 first.

Complexity

Time: O(n log n). Each monster is enqueued at most once and dequeued at most once, each in O(log n). The inner while loop runs once per potion used, never more than once per queued monster.

Space: O(n). In the worst case the heap holds every monster that dealt damage.

Edge cases and common mistakes

No potions. With K = 0 the hero simply loses health in order. For damage = [1, 2], HP = 10 and K = 0 the answer is 2. For [5, 5] with HP = 5 the first monster takes health to exactly 0, so the answer is 1.
Exactly zero health. Reaching 0 while defeating a monster counts that monster as killed (i + 1), but the hero cannot fight on. Returning i in that case would miss one monster.
Healing monsters in the heap. A monster with zero or negative damage does not belong in the heap. A potion spent on it would subtract health instead of refunding it.
Using a potion too early. Spending potions as soon as a monster looks dangerous wastes them. The retroactive rule always picks the biggest hit so far.
Counting off by one. The index i is zero-based, so the monsters before index i number exactly i.
Healing after death. The check for death comes inside the loop right after each fight. A healing monster later in the array can't bring a dead hero back, because the method has already returned.

Testing

damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3], K = 2, HP = 10 gives 8.
damage = [5, 5], K = 0, HP = 5 gives 1.
damage = [5, 5], K = 1, HP = 5 gives 2.
damage = [1, 2], K = 0, HP = 10 gives 2.

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