Start learning free

LESSON 318 OF 414 · HEAP

Kill Monsters in Scala: A Greedy Max-Heap Solution

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

    SCALA · HEAP

    Kill Monsters in Scala, explained

    Problem overview

    A hero starts with HP health points and K magic potions, and fights monsters in the given order. The array damage holds what each monster does: a positive number takes health away, a negative number gives health back. A potion kills a monster instantly, so the hero loses nothing for it. The hero dies when health reaches zero or below, and the method killMonsters(damage, K, HP) returns the largest number of monsters killed, with the potions used as well as possible.

    In the example, K = 2, HP = 10 and damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3]. The answer is 8.

    Approach: fight first, spend potions in hindsight

    The question is where to spend the potions. The natural choice is the monsters that deal the most damage, but you only learn how bad a monster is as you meet it, and a potion decision at monster 3 may look different once monster 6 appears.

    The solution postpones the decision. It fights every monster normally and remembers the damage of each monster fought in a max heap. Only when health drops to zero or below does it spend a potion, and it spends it retroactively on the monster that hurt the most so far, which is the top of the heap. Using the potion on that monster would have saved the most health, so the health goes back up by exactly that damage. If there are no potions left, or the heap is empty, the hero cannot survive and the loop stops.

    Here is the example, traced:

    idamageHP afterwardspotions left
    0-3132
    12112
    2382
    3-2102
    4822
    5821
    6640
    7400

    At i = 5 the fight takes HP to -6, so a potion goes retroactively to an 8, the largest damage so far, and HP returns to 2. At i = 6 HP falls to -4, and the second potion goes to the other 8. At i = 7 the hero ends at exactly 0 HP with no potions, and the method returns 8, the number of monsters up to and including index 7.

    Step by step

    1. Copy the inputs into variables. The starter code declares var k = K and var hp = HP, because method parameters can't be reassigned in Scala.
    2. Create the heap. Declare kills as a val holding an empty PriorityQueue[Int]. The mutable PriorityQueue dequeues its largest element first, so it is already a max heap.
    3. Loop over the indices with for (i <- damage.indices). The index is needed because the answer is a count of monsters.
    4. Healing monsters. If damage(i) <= 0, do hp += -damage(i). Such a monster never needs a potion and never goes into the heap. Scala has no continue, so the rest of the body goes in the else branch.
    5. Fight. In the else branch, subtract damage(i) from hp.
    6. Remember the fight. Call kills.enqueue(damage(i)), so a potion can still be applied to this monster later.
    7. Spend potions while needed. A while loop runs as long as hp <= 0 && k > 0 && kills.nonEmpty.
    8. Use a potion on the worst monster. Inside the loop, hp += kills.dequeue() and k -= 1. Scala has no --.
    9. Death. After the loop, if (hp < 0) return i. Even with potions the hero can't survive monster i, so only the i monsters before it count. Indexes start at 0, so i is also that count.
    10. Exactly zero. if (hp == 0) return i + 1. The loop leaves HP at exactly 0 only when no potion could be used, and the lesson counts monster i as killed, then ends the run.
    11. Survived everything. After the for loop, return damage.length.

    The solution in Scala

    class Solution {
    def killMonsters(damage: Array[Int], K: Int, HP: Int): Int = {
        var k = K
        var hp = HP
        val kills = PriorityQueue[Int]()
        for (i <- damage.indices) {
            if (damage(i) <= 0) {
                hp += -damage(i)
            } else {
                hp -= damage(i)
                kills.enqueue(damage(i))
                while (hp <= 0 && k > 0 && kills.nonEmpty) {
                    hp += kills.dequeue()
                    k -= 1
                }
                if (hp < 0) {
                    return i
                }
                if (hp == 0) {
                    return i + 1
                }
            }
        }
        return damage.length
    }
}

    The Scala details worth a closer look:

    • Parameters are values. K and HP can be read but not reassigned, which is why the code works on the copies k and hp.
    • The import. PriorityQueue lives in scala.collection.mutable. A standalone file needs import scala.collection.mutable.PriorityQueue.
    • return inside for. The two return statements are inside the body of a for loop, so they leave the whole method. Scala 3.5 accepts this and prints a warning that non-local returns are no longer supported. The code still compiles and returns the right values.
    • Zero damage. A monster with damage(i) == 0 takes the first branch, adds 0 to hp and is never put in the heap, which is fine because a potion on it would save nothing.
    • Unary minus. hp += -damage(i) adds the negated damage, so a negative damage raises HP.

    Complexity

    Time: O(n log n). Each monster is enqueued at most once, and each potion dequeues one entry, so there are at most n enqueues and at most min(K, n) dequeues, each O(log n).

    Space: O(n). The heap can hold every monster that dealt damage.

    Edge cases and common mistakes

    • No monsters. An empty array returns 0, which equals damage.length.
    • Damage equal to HP, no potions. damage = [5], K = 0, HP = 5 returns 1 through the hp == 0 branch. With HP = 4 it returns 0, and with HP = 6 it returns 1 through the final line.
    • A potion fixes the current monster. damage = [5], K = 1, HP = 5: HP drops to 0, the potion goes to this very monster, HP is back at 5 and the method returns 1.
    • The potion goes to an earlier monster. damage = [4, 6, 5], K = 1, HP = 8: after the 6, HP is -2, and the potion is applied to the 6, restoring HP to 4. The 5 then takes HP to -1, so the method returns 2.
    • Several potions on small hits. [9, 9, 9] with K = 2 and HP = 10 returns 3: each 9 after the first is cancelled by a potion.
    • Putting healing monsters in the heap. A potion "used" on one would subtract health instead of adding it.
    • Using a min heap. A potion would go to the smallest damage and save the least health.
    • Using a potion before HP runs out. Deciding early can't be corrected later. Waiting for HP to drop to zero keeps every choice open.

    Testing

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