Last Stone Weight
Smash the two heaviest stones until at most one is left, using a max-heap to find the heaviest pair each round.
Problem Understanding
Last Stone Weight: each turn, take the two heaviest stones y ≥ x and smash them. If they are equal both are destroyed; otherwise a stone of weight y − x is left. Repeat until at most one stone remains and return its weight, or 0.
Example: [2, 7, 4, 1, 8, 1] returns 1.
The Intuition: Always Ask for the Two Heaviest
The rules decide everything; the only question is how to find the two heaviest stones quickly, round after round, while new stones keep appearing.
Sorting once is not enough, because the new stone y − x can land anywhere. A max-heap is built for exactly this: pop the largest in O(log n), push any value in O(log n).
- Heapify all the stones.
- While at least two remain: pop
y, popx; ify != x, pushy − x. - Return the remaining stone, or
0.
Each round removes at least one stone, so there are at most n rounds.
Interactive Walkthrough
The heap's contents are listed heaviest first, which is the order it hands them out. Each round, the two stones popped appear in the smashed row with what they leave behind, and the new stone is highlighted where it lands.
Dry Run Table
Input: [2, 7, 4, 1, 8, 1]
| Heap (heaviest first) | y, x | Result |
|---|---|---|
| 8, 7, 4, 2, 1, 1 | 8, 7 | push 1 |
| 4, 2, 1, 1, 1 | 4, 2 | push 2 |
| 2, 1, 1, 1 | 2, 1 | push 1 |
| 1, 1, 1 | 1, 1 | both gone |
| 1 | — | return 1 |
The Solution Template
A max-heap where the language has one. JavaScript has no built-in heap; with at most 30 stones, a sorted array does the same job.
Last Stone Weight Code
1var lastStoneWeight = function(stones) {2 const heap = [...stones].sort((a, b) => a - b);3 while (heap.length > 1) {4 const y = heap.pop();5 const x = heap.pop();6 if (y !== x) {7 const d = y - x;8 const i = heap.findIndex((v) => v >= d);9 heap.splice(i === -1 ? heap.length : i, 0, d);10 }11 }12 return heap.length ? heap[0] : 0;13};
Edge Cases & Common Mistakes
- One stone: the loop never runs; return it.
- Everything cancels: return
0when the heap is empty, instead of readingheap[0]. - Python's min-heap: forgetting to negate pops the lightest stones instead of the heaviest.
- Sorting once at the start: the new stone
y − xmust go back in its place, or the next round picks the wrong pair.
Summary
Keep the stones in a max-heap. Pop the two heaviest, push back their difference if it is not zero, and repeat until at most one stone remains. O(n log n) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet