Start learning free

LESSON 317 OF 414 · HEAP

Last Stone Weight in Scala: Simulating the Smashes with a Max Heap

Practice O(n log n) Read the full explanation

We have a collection of stones, where each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has the new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

 

Example: 

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
STEP 1 OF 8
    Ctrl + Enter to check

    SCALA · HEAP

    Last Stone Weight in Scala, explained

    Problem overview

    The method lastStoneWeight receives an Array[Int] of positive stone weights. Each turn the two heaviest stones are smashed together. If they weigh the same, both disappear. If they differ, the lighter one disappears and the heavier one is left with the difference of the two weights. The process repeats until at most one stone remains, and the method returns that stone's weight, or 0 if no stone is left.

    For [2, 7, 4, 1, 8, 1] the smashes go like this:

    1. 8 and 7 leave a 1, so the stones are 2, 4, 1, 1, 1.
    2. 4 and 2 leave a 2, so the stones are 2, 1, 1, 1.
    3. 2 and 1 leave a 1, so the stones are 1, 1, 1.
    4. 1 and 1 destroy each other, leaving one stone of weight 1.

    The answer is 1.

    Approach: always grab the heaviest two

    Each turn needs the two largest weights, and then a new, smaller weight goes back in. Sorting once isn't enough, because the new stone belongs somewhere in the middle of the order. Re-sorting after every smash would cost O(n log n) per turn. A max heap fits better: it returns its largest element quickly and accepts new elements quickly, each in O(log n).

    So the plan is to put all stones in a max heap, then repeat: take the largest, take the next largest, and if they differ, put their difference back. Every turn removes at least one stone from the heap (two out, at most one in), so the loop ends after fewer than n turns.

    Seen from the heap's side, the example looks like this, with the largest weight first:

    start:        8 7 4 2 1 1
smash 8, 7:   4 2 1 1 1
smash 4, 2:   2 1 1 1
smash 2, 1:   1 1 1
smash 1, 1:   1

    Each line is what a sorted view of the heap contains after that smash. The heap itself doesn't keep a fully sorted array, only enough order to find the largest element fast.

    Step by step

    1. Create the heap. Declare heap with val as PriorityQueue[Int](). Scala's mutable PriorityQueue is a max heap by default, so the heaviest stone is on top and no custom ordering is needed.
    2. Load the stones with heap.addAll(stones). It inserts every element of the array into the heap.
    3. Loop while two stones remain: while (heap.size >= 2). When the loop ends there are zero or one stones.
    4. Take the heaviest stone into val x = heap.dequeue(). dequeue() removes the top value and returns it.
    5. Take the second heaviest into val y = heap.dequeue(). Since x came out first, x >= y.
    6. Push the remainder. If x != y, call heap.enqueue(x - y). Equal stones destroy each other, so nothing goes back.
    7. Handle the empty case. After the loop, if heap.size == 0, return 0. heap.isEmpty means the same.
    8. Otherwise return heap.head, the last stone. head reads the top without removing it.

    The solution in Scala

    class Solution {
    def lastStoneWeight(stones: Array[Int]): Int = {
        val heap = PriorityQueue[Int]()
        heap.addAll(stones)
        while (heap.size >= 2) {
            val x = heap.dequeue()
            val y = heap.dequeue()
            if (x != y) {
                heap.enqueue(x - y)
            }
        }
        if (heap.size == 0) {
            return 0
        }
        return heap.head
    }
}

    The Scala details worth a closer look:

    • The import. PriorityQueue is in scala.collection.mutable. A standalone file needs import scala.collection.mutable.PriorityQueue above the class.
    • Calling the constructor without new. PriorityQueue[Int]() works in Scala 3 and calls the companion's apply. The queue gets its ordering from the implicit Ordering[Int], which puts bigger numbers first. For a min heap you would write PriorityQueue[Int]()(Ordering[Int].reverse).
    • addAll copies. After heap.addAll(stones), the heap holds its own copy of the values. The array stones is not changed, and later changes to the heap don't touch it.
    • Empty queues throw. dequeue() and head on an empty queue throw NoSuchElementException. The code is safe because the loop checks heap.size >= 2 before the two dequeue() calls, and the final if handles an empty heap before head.
    • No ++ or --. Not needed here, but remember that Scala has none. Use += 1.

    Complexity

    Time: O(n log n). Loading the stones costs n insertions of O(log n) each. The loop runs fewer than n times, and each run does two removals and at most one insertion, each O(log n).

    Space: O(n). The heap holds up to n stones.

    Edge cases and common mistakes

    • No stones. An empty array skips the loop and returns 0.
    • One stone. [5] skips the loop and returns 5.
    • Two equal stones. [3, 3] returns 0.
    • Everything cancels. [9, 3, 2, 10] returns 0: 10 and 9 leave 1, then 3 and 2 leave 1, and the two 1s cancel.
    • An odd number of equal stones. [1, 1, 1] returns 1.
    • Pushing back zero. Without the x != y test, a stone of weight 0 would enter the heap, although the rules say equal stones are destroyed. It would also be counted by heap.size and cost extra turns.
    • Reading head too early. Using head instead of dequeue() inside the loop leaves the stones in the heap, so the loop would never finish.
    • Printing the heap to debug. A PriorityQueue prints its internal layout, not the sorted order, so printed output can look unsorted even when the heap is correct.

    Testing

    • stones = [2, 7, 4, 1, 8, 1] gives 1.
    • stones = [] gives 0.
    • stones = [5] gives 5.
    • stones = [3, 3] gives 0.
    • stones = [9, 3, 2, 10] 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