Last Stone Weight
Repeatedly smash the two heaviest stones together; equal weights destroy both, otherwise the difference remains. Return the weight of the last stone, or 0.
Open on LeetCode ↗Intuition
The naive approach re-sorts the whole list after every smash just to find the new top two, which is O(n^2 log n) and throws away work the previous sort already did. The operation only ever needs the two largest values and feeds one value back in, which is a max-heap almost verbatim — pop twice, push the difference if non-zero, repeat until at most one stone remains. Python's heapq is min-heap only, so every weight has to go in negated, and it's easy to smash correctly but forget to negate the final answer back on the way out, returning a negative weight.
Repeatedly needing the two largest values is the signature of a max-heap. Python only ships a min-heap, so negating on the way in and out simulates one — a standard idiom worth recognising instantly.
Approach
Match the data structure to the operation
Every round needs the two maxima and then inserts a new value. A sorted list gives O(n) insertion per round, while a heap gives O(log n) for both the pops and the push — the deciding factor once the number of rounds grows.
Negate for Python's min-heap
heapq is a min-heap only, so store negated weights and negate again on the way out. Alternatively use a language with a max-heap directly, but the negation trick is worth knowing because it comes up constantly in Python solutions.
Smash until one or none remains
While at least two stones are present, pop a and b (the two largest). If they differ, push a - b back. If they are equal, push nothing — both are destroyed. When the loop ends, return the single remaining stone or 0 for an empty heap. Building the heap is O(n) and each of at most n rounds costs O(log n), so the total is O(n log n) time and O(n) space.
Solution & live demo
Common pitfalls
Re-sorting after every smash
stones.sort() a, b = stones.pop(), stones.pop()
a = -heapq.heappop(heap)
That's O(n log n) per smash for O(n) smashes. A heap restores its invariant in O(log n), which is the whole reason to use one here.
Pushing a zero back
heapq.heappush(heap, -(a - b))
if a != b:
heapq.heappush(heap, -(a - b))Equal stones destroy each other completely. Pushing the zero leaves a phantom stone that keeps the loop running and can be returned as the final answer.
Indexing the heap for the maximum
return max(heap)
return -heap[0] if heap else 0
heap[0] is the root and is the correct element here, but only because at most one stone remains. In general a heap's internal order is unspecified beyond the root — never read other positions expecting sorted order.
Edge cases
The loop never runs and that stone's weight is returned.
They pair off and destroy each other completely, so the answer is 0.
One survives, so the answer is that weight.
The answer comes back negative — the classic slip with the negated-heap trick.