← Back to DSA Animator
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.