Each turn, take the two heaviest stones, x ≤ y. If they are equal, both are destroyed; otherwise the lighter is destroyed and the heavier becomes y − x. Return the weight of the last stone, or 0 if none remains.
Before you code
Re-sorting after every smash costs O(n log n) per turn. A max-heap gives the two heaviest in O(log n) each and takes the remainder back in O(log n).
Hints
- Python's heapq is a min-heap: push negated weights.
- Each turn: pop two, and if they differ, push the difference.
- Stop when at most one stone is left.
Production & complexity notes
When solving Last stone weight on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Sift-up and sift-down to reinforce the underlying pattern.
What it practices
Push and pop with sift-up and sift-down, from Sift-up and sift-down.