Last Stone Weight: Smashing Stones with a Max-Heap
Solve Last Stone Weight with a max-heap — repeatedly smash the two heaviest stones, with a worked walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Last Stone Weight reads like a physics puzzle: you have a pile of stones, you keep smashing the two heaviest together, and you want to know what's left at the end. The catch is that the "two heaviest" change every single round. Pick the wrong data structure and you're re-sorting the whole pile every turn.
The trick is recognizing that you never need the pile sorted — you only ever need the top two. That's exactly what a heap is built for, and this problem is one of the cleanest ways to internalize why a priority queue exists.
The problem
You're given an array stones where each value is the weight of a stone. On each turn you take the two heaviest stones, weights y and x with y >= x, and smash them:
- If
y === x, both stones are destroyed. - If
y !== x, the stone of weightxis destroyed and the heavier one keeps weighty - x.
Repeat until one stone or zero stones remain. Return the weight of that last stone (or 0 if none survive).
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Smash 8 and 7 -> 1 left: [2, 4, 1, 1, 1]
Smash 4 and 2 -> 2 left: [2, 1, 1, 1]
Smash 2 and 1 -> 1 left: [1, 1, 1]
Smash 1 and 1 -> 0 left: [1]The last stone weighs 1.
The brute force baseline
Without a heap, "grab the two heaviest" means finding the maximum, removing it, finding the max again, and removing that too. The simplest version just re-sorts on every round.
function lastStoneWeight(stones) {
const pile = [...stones];
while (pile.length > 1) {
pile.sort((a, b) => a - b); // ascending
const y = pile.pop(); // heaviest
const x = pile.pop(); // second heaviest
if (y - x > 0) pile.push(y - x);
}
return pile.length ? pile[0] : 0;
}This is correct, but wasteful. Each round throws away a full O(n log n) sort just to learn the top two values. In the worst case you run close to n rounds, so the total cost balloons to O(n² log n). You're paying to order the entire pile when you only ever look at its two largest elements.
The key insight: you only need the top
Sorting answers a question you never asked. You don't care about the order of the small stones — you care about repeatedly pulling the single largest, twice per round, and then dropping a new value back in.
A max-heap (max priority queue) does precisely this:
peek/dequeuereturns the maximum inO(log n).enqueueinserts a new value and restores order inO(log n).
So each smash round is two dequeues and at most one enqueue — three O(log n) operations instead of a full sort. The heap keeps the heaviest stone at the root at all times, so the "two heaviest" are always one dequeue apart. This is the core heap simulation pattern: when a problem repeatedly asks for the current extreme of a changing set, reach for a priority queue.
The optimal solution
Build a max priority queue from the stones, then loop while more than one stone remains, dequeuing y then x and pushing back the positive difference.
var lastStoneWeight = function (stones) {
let pq = new MaxPriorityQueue();
for (let i = 0; i < stones.length; i++) pq.enqueue(stones[i]);
while (pq.size() > 1) {
let y = pq.dequeue();
let x = pq.dequeue();
if (y - x > 0) pq.enqueue(y - x);
}
return pq.dequeue() || 0;
};Two things make this clean. First, because the heap always returns the maximum, the first dequeue is guaranteed to be y (the heaviest) and the second is x (the next heaviest) — no comparison needed to decide which is bigger. Second, the if (y - x > 0) guard silently handles the equal case: when y === x the difference is 0, the branch is skipped, and both stones stay gone. Only a genuine remainder re-enters the pile.
When the loop ends, either one stone is left (return it) or none is (pq.dequeue() is falsy, so || 0 returns 0).
If your language's built-in is a min-heap (like Python's heapq), the standard workaround is to negate every value on the way in and negate again on the way out, which turns min-behavior into max-behavior without writing your own heap.
Walkthrough
Tracing stones = [2, 7, 4, 1, 8, 1]. The heap column shows the multiset of remaining weights, heaviest first; y and x are the two dequeued stones each round.
| Round | Heap before | y | x | y - x | Action | Heap after |
|---|---|---|---|---|---|---|
| 1 | 8, 7, 4, 2, 1, 1 | 8 | 7 | 1 | push 1 | 4, 2, 1, 1, 1 |
| 2 | 4, 2, 1, 1, 1 | 4 | 2 | 2 | push 2 | 2, 1, 1, 1 |
| 3 | 2, 1, 1, 1 | 2 | 1 | 1 | push 1 | 1, 1, 1 |
| 4 | 1, 1, 1 | 1 | 1 | 0 | both destroyed | 1 |
| — | 1 | — | — | — | size is 1, stop | 1 |
Round 4 is the case worth watching: y - x is 0, so nothing is pushed back and the heap shrinks by two in a single round. After it, only one stone remains and the loop condition size() > 1 fails. The survivor weighs 1, which is the answer.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Sort every round | O(n² log n) | O(n) | up to n rounds, each doing a full O(n log n) sort |
| Max-heap simulation | O(n log n) | O(n) | heapify plus up to n rounds of O(log n) heap ops |
Building the heap costs O(n) (or O(n log n) if you enqueue one at a time). Each round removes at least one stone and does a constant number of O(log n) heap operations, so with at most n rounds the loop is O(n log n). The heap itself holds up to n values, giving O(n) space.
Common mistakes
- Reaching for a sort inside the loop. It works but drags you to
O(n² log n). The whole point is that you need the top element, not a sorted array. - Building a min-heap and forgetting to negate. A raw min-heap hands you the two lightest stones. If you use
heapqin Python, push-weightand flip the sign back when you pop. - Pushing back when the stones are equal. Guard the enqueue with
y - x > 0. Pushing a0would leave a phantom zero-weight stone in the pile and can throw off the final answer. - Mishandling the empty pile. After the loop, the heap may be empty (every stone annihilated). Return
0in that case —pq.dequeue() || 0covers it, but a barepq.dequeue()returnsundefined. - Assuming
y >= xneeds a manual check. Because the max-heap returns values in non-increasing order, the first pop is always>=the second. No swapping required.
Where this pattern shows up next
The "repeatedly pull the extreme from a changing set" idea powers a whole family of heap problems:
- Min-Heap Operations — the mechanics of the data structure underneath this solution: sift-up, sift-down, and why they're
O(log n). - Kth Largest Element in an Array — a heap that keeps only the top
k, instead of draining down to one. - Kth Largest Element in a Stream — the same top-
kheap, maintained live as new numbers arrive. - Kth Smallest Element in a Sorted Matrix — a min-heap pulling the next-smallest candidate across sorted rows.
You can also step through Last Stone Weight interactively to watch the max-heap re-heapify after each smash and see the graveyard of destroyed stones fill up round by round.
FAQ
Why use a heap instead of just sorting the stones?
Sorting orders every stone, but the problem only ever needs the two heaviest each round — and the pile changes after every smash, so a static sort goes stale immediately. A max-heap gives you the maximum in O(log n) and lets you insert the remainder in O(log n), so each round is a few log-time operations instead of a fresh O(n log n) sort. That drops the total from O(n² log n) to O(n log n).
What happens when the two heaviest stones are equal?
Both stones are destroyed and nothing goes back into the heap. In code this is handled by the if (y - x > 0) guard: when y === x the difference is 0, the enqueue is skipped, and the pile simply shrinks by two. Forgetting the guard and pushing a 0 back is a common bug, because it leaves a fake zero-weight stone that can survive to the end.
What is the time and space complexity of the max-heap solution?
Time is O(n log n) and space is O(n). Building the heap is O(n), and the smash loop runs at most n rounds since every round removes at least one stone; each round does a constant number of O(log n) heap operations. The heap stores up to n weights, which accounts for the O(n) space.
How do I do this in a language that only has a min-heap?
Negate the weights. Push each stone as its negative value, and the min-heap's smallest (most negative) element is the largest real weight. When you pop, negate again to recover the true weight. Python's heapq is the classic case: heappush(h, -weight) and y = -heappop(h) turns it into a max-heap with no custom code.
Does the last stone weight ever have more than one answer?
No — the process is deterministic. At every step the two heaviest stones are uniquely determined by their weights (ties don't matter, since equal stones just annihilate each other), so the sequence of smashes and the final surviving weight are fixed for any given input. If the pile fully annihilates, the answer is 0; otherwise it's the single remaining stone.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.