The problem
You have rocks with weights. Each turn, smash the two heaviest together: if they weigh the same both are destroyed, otherwise the lighter is destroyed and the heavier loses that much weight. Return the weight of the last rock left, or 0.
Input: [2, 7, 4, 1, 8, 1] Output: 1
Picture it
Picture a pile of rocks arranged so the heaviest is always on top: a max-heap. Each round we lift off the top two, smash them, and if anything is left over it goes back onto the pile, which re-sorts itself so the heaviest is on top again.
How to recognise it
- Each step needs the largest item (here the two largest), and the result of the step goes back into the pile.
- The pile changes after every step, so a sort done once at the start is not enough.
- The process repeats until a simple stop condition: at most one item left.
- "Always take the biggest" plus "put something back" is the textbook signature of a priority queue (a structure that always hands out its best item first). In practice that is a heap, a tree stored in a list with O(log n) push and pop.
- The limits here are small (at most 30 stones of weight up to 1000), so the exercise is about the pattern, not about beating a time limit.
Start with brute force
Keep the stones in a list. Every round, sort it, remove the two heaviest, and add the leftover if they differ.
def last_stone_weight_brute(stones):
s = list(stones)
while len(s) > 1:
s.sort()
a = s.pop() # heaviest
b = s.pop() # second heaviest
if a != b:
s.append(a - b)
return s[0] if s else 0
Every round sorts up to n numbers, and there are up to n − 1 rounds, so time is O(n² log n) and extra space is O(n) for the copy. With n = 30 that is trivial. If the same rule were applied to 10^5 stones it would be about 10^5 rounds of sorting up to 10^5 numbers, around 10^11 steps, which is hopeless.
From brute force to the idea
- Find the waste. A full sort puts all n stones in order, but each round only needs the top two.
- Use a structure that serves the biggest. A heap gives the extreme item in O(log n) and accepts a new item in O(log n).
- Work around Python's min-heap.
heapqalways returns the smallest. Store each weight negated: the most negative number is the heaviest stone. - Smash. Pop twice (negating back to get
aandb, witha >= b). Ifa != b, push the leftovera - b, negated. - Finish. When fewer than two stones remain, return the single one (negated back) or 0 if the heap is empty.
This is the key idea: a max-heap (negated min-heap) serves the two heaviest stones in O(log n) each.
The key idea
A max-heap hands over the two largest in O(log n) each; repeat until at most one rock remains.
Python solution
def last_stone_weight(stones):
heap = [-s for s in stones] # max-heap via negatives
heapify(heap)
while len(heap) > 1:
a = -heappop(heap) # heaviest
b = -heappop(heap) # second heaviest
if a != b:
heappush(heap, -(a - b)) # what’s left of the bigger rock
return -heap[0] if heap else 0LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop, heapify
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n² log n): up to n rounds, each with a sort | O(n): the copied list |
| Max-heap (shown code) | O(n log n): heapify is O(n), then at most n − 1 rounds of two pops and one push, each O(log n) | O(n): the negated copy of the stones |
Edge cases
- One stone (
[5]): the loop never runs and the answer is 5. - Two equal stones (
[4, 4]): both are destroyed, the heap is empty, and the final guard returns 0. - All destroyed along the way (
[1, 3, 2]): 3 and 2 leave 1, then 1 and 1 cancel, so the answer is 0. - Empty list: returns 0, because of the
if heap else 0guard. The problem promises at least one stone. - Input is not changed: the heap is built from a new list.
- Imports: the shown code needs
from heapq import heapify, heappush, heappop.
Common mistakes
- Pushing a positive
a - bonto the negated heap, which treats the leftover as the lightest stone. - Forgetting to negate after popping, so
aandbare negative and the difference is wrong. - Dropping the
if heap else 0guard. When every stone cancels out,heap[0]raisesIndexError. - Re-sorting the list each round "to keep it simple". It works at n = 30 but hides the point of the exercise.
Use the same rules, but return how many smashes happen before at most one stone remains. For [2, 7, 4, 1, 8, 1] the answer is 4. Describe your approach, then write it if you like.
Compare with our answer
The heap loop is unchanged. Add a counter that goes up by one every time two stones are taken out. Nothing else matters, because each smash removes one or two stones.
from heapq import heapify, heappush, heappop
def count_smashes(stones):
heap = [-s for s in stones]
heapify(heap)
smashes = 0
while len(heap) > 1:
a = -heappop(heap)
b = -heappop(heap)
smashes += 1
if a != b:
heappush(heap, -(a - b))
return smashes
count_smashes([4, 4]) is 1 and count_smashes([1]) is 0. Time O(n log n), space O(n).
A strong answer mentions: keeping the same max-heap loop, counting once per pair taken out, and that the number of smashes is at most n − 1.
1. A call centre always serves the longest-waiting customer next, and unfinished calls rejoin the queue with a new waiting time. Which structure fits best?
Each step needs the current extreme item and then re-inserts a changed one, which is what a heap does in O(log n). A plain queue ignores the changed waiting times, and scanning a map costs O(n) per step.
2. Why is the shown solution O(n log n) while the brute force is O(n² log n)?
The number of rounds is the same (at most n − 1). The saving is that the heap serves the top two in O(log n), not by sorting everything each time. The heaviest stone does change, and the leftover goes back in.
3. A learner deletes the if heap else 0 guard and returns -heap[0] always. Which input now crashes?
After [4, 4] both stones are destroyed, the heap is empty, and heap[0] raises IndexError. The other inputs each leave one stone behind.
Score 60% or more and the lesson is marked complete.