DSA AnimatorDSA animations
Last Stone Weight LC #1046 Easy Heap · Max Heap
Problem

You have a collection of stones, each with a positive integer weight. Each turn, choose the two heaviest stones and smash them together. Suppose the heaviest is a and the second heaviest is b. If a == b both are destroyed; if a != b, stone of weight a is destroyed and stone of weight b becomes a - b. Return the weight of the last remaining stone, or 0 if none remain.

Example 1
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 8,7→1; 1,4→3; 3,2→1; 1,1→0 (destroyed); last stone=1.
Example 2
Input: stones = [1]
Output: 1
Example 3
Input: stones = [3,3]
Output: 0
Constraints: 1 ≤ stones.length ≤ 30  |  1 ≤ stones[i] ≤ 1000
Try Examples
Custom:
Approach
Max Heap Simulation — Always Smash the Two Heaviest
A max-heap gives the two largest in O(log n). Repeat until 1 or 0 stones remain.
Stone Heap
Round 0
Smash Arena
Stone A (heavier)
—
Stone B (lighter)
—
Variables
a (heavier)
—
b (lighter)
—
diff (a − b)
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🪨
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Build a max-heap from all stones using PriorityQueue(reverseOrder)
2
Poll a = largest, then b = 2nd largest from the heap
3
If a ≠ b: push (a − b) back; if a == b: both destroyed, nothing pushed
4
Repeat until ≤ 1 stone remains. Return last stone or 0
Time
O(n log n)
Space
O(n)
Why Max Heap?

We always need the two largest elements, and the heap gives us each in O(log n). With at most n rounds (each removes at least one stone), the total cost is O(n log n). A sorted array would need O(n) per round for insertion — the heap is the natural fit.

How to solve Last Stone Weight

LeetCode 1046 · Easy · Heap / Priority Queue · Pattern: Max Heap Simulation

Why the obvious approach is slow

You could sort the stones again after every smash. That costs O(n log n) per turn, so O(n²) log n overall. We only ever need the two biggest values, which is exactly what a max heap gives us.

The key idea

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.

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.

Run the animation above on your own input, or watch the 2:03 video explanation of Last Stone Weight with a dry run and Java code.

More Heap / Priority Queue problems