Last Stone Weight

You are given an array stones of positive weights. On each turn, take the two heaviest stones, with weights y and x where x <= y, and smash them together:

The game ends when at most one stone is left. Return its weight, or 0 if no stone is left. Limits: 1 <= stones.length <= 30 and 1 <= stones[i] <= 1000. This is LeetCode 1046.

Example 1
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Example 2
Input: stones = [1]
Output: 1
Example 3
Input: stones = [2, 2]
Output: 0

How to Think About It

Step 1: There is nothing to choose

The rules fix which two stones meet on every turn, so the task is pure simulation. The only question is how to find the two heaviest stones quickly, again and again.

Step 2: Sorting once is not enough

A smash can create a new stone of weight y - x, and that stone can be lighter than some stones and heavier than others. Sorting the array once and then popping from the end ignores where the new stone belongs. On Example 1 that shortcut returns 0 instead of 1.

Re-sorting after every turn is correct but costs O(n log n) per turn, which is O(n² log n) in total.

Step 3: A max-heap matches the operations

Each turn removes the two largest values and maybe inserts one new value. A max-heap does exactly these three operations in O(log n) each. The heap introduction explains how poll and offer keep the largest value on top.

Step 4: The game always ends

Every turn removes at least one stone, because two come out and at most one goes back. With n stones there are at most n - 1 turns.

Walkthrough

Example 1, stones = [2, 7, 4, 1, 8, 1]. The heap is listed from heaviest to lightest.

Turny (heaviest)x (second)Pushed backHeap after
1871[4, 2, 1, 1, 1]
2422[2, 1, 1, 1]
3211[1, 1, 1]
411nothing, both destroyed[1]

One stone of weight 1 remains, so the answer is 1.

Java Solution

lastStoneWeight loads every stone into a max-heap and plays turns until fewer than two stones remain.

  • Making it a max-heap: Java's PriorityQueue puts the smallest value on top, so Collections.reverseOrder() is passed to flip it.
  • Order of the polls: the first poll gives y and the second gives x, so y - x is never negative.
  • Equal stones: nothing is pushed when y == x. For [2, 2] the heap becomes empty and the method returns 0.
  • The return value: the loop stops with zero or one stone, so isEmpty() picks between 0 and peek(). A single stone such as [1] never enters the loop and is returned as is.

A common mistake is to forget Collections.reverseOrder(). The default min-heap then polls the two lightest stones, so y is never larger than x and nothing is pushed back. Stones just vanish in pairs, and Example 1 returns 0 instead of 1.

Java
import java.util.Collections;
import java.util.PriorityQueue;

public class LastStoneWeight {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
        for (int s : stones) heap.offer(s);
        while (heap.size() > 1) {
            int y = heap.poll();          // heaviest
            int x = heap.poll();          // second heaviest, so x <= y
            if (y > x) heap.offer(y - x); // equal stones both disappear
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

Complexity

  • Time: O(n log n). Building the heap takes n offers, and there are at most n - 1 turns, each with two polls and at most one offer on a heap of at most n stones.
  • Space: O(n) for the heap. It starts with all n stones and only shrinks, since every turn removes at least one stone.

The code matched a re-sort-every-turn reference on 50,000 random inputs. Another problem where a max-heap drives a greedy process is IPO, and keeping only some values in a heap appears in K Closest Points to Origin.