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.
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
Intuition
Last stone weight repeatedly smashes the two heaviest stones together. Equal stones destroy each other; unequal ones leave a stone of the difference. The process repeats until at most one remains.
The operation needed is always the same — retrieve the two largest values, then possibly insert a new one. Sorting after every smash is O(n² log n) and does far more work than required, since only the top two matter.
A max-heap provides exactly that:
- A max-heap gives the largest element in O(log n) and accepts the new stone in O(log n), which is all this simulation needs.
Each round pops twice. If the weights differ, push the difference back; if they are equal, push nothing, since both stones are destroyed.
Pushing a zero when the stones are equal is the common bug. It leaves a phantom stone in the heap, and the final answer becomes 0 when it should be the weight of a genuinely surviving stone — or the loop reports a stone that no longer exists.
The loop continues while more than one stone remains. At the end, return the last stone's weight, or 0 if the heap emptied.
Languages providing only a min-heap — Python's heapq among them — require negating values on insertion and negating again on removal. Forgetting either negation silently selects the smallest stones instead of the largest.
Each round removes at least one stone, so the process terminates after at most n rounds.
Last Stone Weight II looks similar but is entirely different — a partition problem solved with subset-sum DP, not a simulation.
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
Before reading on: price up what the direct approach costs here, then ask why only the extreme element matters and the rest need no ordering. Aim for O(n log n) time and O(n) space.
Identify the repeated operation
Every round needs the two largest stones and may insert one more. Re-sorting each round does far more work than that requires.
Use a max-heap
A max-heap retrieves the largest in O(log n) and inserts in O(log n) — exactly the two operations the simulation performs.
Smash the top two
Pop twice each round. If the weights differ, push the difference back; if equal, both stones are destroyed and nothing is pushed.
Never push a zero
Pushing 0 for equal stones leaves a phantom stone, making the final answer 0 when a real stone survives. Push only when the difference is non-zero.
Negate for a min-heap language
Where only a min-heap exists, negate on insertion and again on removal. Forgetting either silently smashes the smallest stones instead of the largest.
Return the survivor
Loop while more than one stone remains, then return the last weight, or 0 if the heap is empty. Each round removes at least one stone, guaranteeing termination.
Cost of the simulation
At most n rounds each costing O(log n) gives O(n log n) time and O(n) space. Last Stone Weight II is a subset-sum DP, not a simulation.
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.