You have a collection of stones, each with a weight. Each turn, smash the two heaviest stones together. If they are equal, both are destroyed, otherwise the smaller one is destroyed and the bigger one keeps the difference. Return the weight of the last stone, or 0 if none is left.
DSA Animator › DSA Revision › Heap / Priority Queue › Last Stone Weight
Remember: when you repeatedly need the largest element, use a max heap. In Java, Collections dot reverse order turns a priority queue into a max heap. The video solves Last Stone Weight (LeetCode 1046, Easy) with the Max Heap Simulation pattern from the Heap / Priority Queue topic, and you can replay every step in the interactive Last Stone Weight animation.
You have a collection of stones, each with a weight. Each turn, smash the two heaviest stones together. If they are equal, both are destroyed, otherwise the smaller one is destroyed and the bigger one keeps the difference. Return the weight of the last stone, or 0 if none is left.
For stones 2, 7, 4, 1, 8, 1, the answer is 1.
You could sort the stones again after every smash. That costs O of n log n per turn, so O of n squared log n overall. We only ever need the two biggest values, which is exactly what a max heap gives us.
Put all stones into a max heap. A max heap is a binary tree stored in an array, where every parent is at least as big as its children. So the biggest stone always sits at the root. Poll twice to get the two heaviest stones. If they differ, push the difference back, and repeat while at least two stones remain.
After building the heap, the array is 8, 7, 4, 1, 2, 1, and 8 is at the root. Poll 8 and 7, and their difference, 1, goes back in. The heap becomes 4, 2, 1, 1, 1. Poll 4 and 2, and push back 2. Poll 2 and 1, and push back 1. Now the heap is 1, 1, 1, so poll 1 and 1, which destroy each other. One stone is left, and its weight is 1.
In code, create a priority queue with reverse order, so it behaves as a max heap. Add every stone. While the size is more than 1, poll two stones, and offer the difference if it is not 0. Return the remaining stone, or 0 if the heap is empty. Each poll and offer costs O of log n, so the total is O of n log n.
Remember: when you repeatedly need the largest element, use a max heap. In Java, Collections dot reverse order turns a priority queue into a max heap.