Easy · Max Heap
Understand → Visualise → Practice.
Repeatedly smash the two heaviest stones; equal weights vanish and unequal weights leave their difference. Return the final weight.
A max-heap gives the two heaviest stones in O(log n). Push back their difference if it is non-zero, until at most one stone remains.
Insert every stone (negate values in a min-heap language).
Pop the two largest; if they differ, push the difference.
Return the last stone's weight, or 0 if none are left.
O(n log n) time and O(n) space.
Re-sorting the list after every smash costs O(n log n) per round.
Read the full guide first: Heaps and Priority Queues.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.