Last Stone Weight
You are given an array stonesyxx <= y
- if
, both stones are destroyed;x == y - otherwise the stone of weight
is destroyed and the other one now weighsx .y - x
The game ends when at most one stone is left. Return its weight, or 0 if no stone is left. Limits: 1 <= stones.length <= 301 <= stones[i] <= 1000
Example 1
Output: 1
Example 2
Output: 1
Example 3
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
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 polloffer
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]
| Turn | y (heaviest) | x (second) | Pushed back | Heap after |
|---|---|---|---|---|
| 1 | 8 | 7 | 1 | [4, 2, 1, 1, 1] |
| 2 | 4 | 2 | 2 | [2, 1, 1, 1] |
| 3 | 2 | 1 | 1 | [1, 1, 1] |
| 4 | 1 | 1 | nothing, both destroyed | [1] |
One stone of weight 1 remains, so the answer is 1.
Java Solution
lastStoneWeight
- Making it a max-heap: Java's
puts the smallest value on top, soPriorityQueue is passed to flip it.Collections.reverseOrder() - Order of the polls: the first
givespoll and the second givesy , sox is never negative.y - x - Equal stones: nothing is pushed when
. Fory == x the heap becomes empty and the method returns 0.[2, 2] - The return value: the loop stops with zero or one stone, so
picks between 0 andisEmpty() . A single stone such aspeek() never enters the loop and is returned as is.[1]
A common mistake is to forget Collections.reverseOrder()yx
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