Last Stone Weight, smash by smash

Each turn needs the two heaviest stones. A max-heap keeps the heaviest stone at its root, so we pop twice to get them, smash them, and push any leftover piece back. Repeat until at most one stone is left.

Try:
CALL
1 / 1

Code

The highlighted line runs next. Sift-up and sift-down steps happen inside the library's push and pop, so they stay on the push and pop lines.

Max-heap (heap)

tree view every parent ≥ its children, so the heaviest stone is always on top

array view how the heap is really stored: children of index i are 2i+1 and 2i+2

Smash

Why a heap? Re-sorting after every smash would cost O(n log n) per turn. The heap hands over the heaviest stone in O(log n), so the whole game is O(n log n).

Dry-run trace

Every step as a row. Click a row to jump there.

#ActionRoundDetailheap (array)size

Keyboard: ← → step, Space play or pause. Up to 12 stones, weights 1–999. Real libraries may order the heap array slightly differently, but the root is always the heaviest stone.