Last Stone Weight
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Repeatedly smash the two heaviest stones. Equal stones vanish; otherwise the lighter is destroyed and the heavier loses that much weight. Return the weight of the last stone (0 if none).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which two stones do you need each round? How can you get them without re-sorting?
- Hint 2Python's heap is a min-heap: store negative weights to get the biggest first.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A pile of boxes where you always pick the two heaviest. Re-sorting the whole pile after every smash is tiring. A heap is like a helper who always keeps the heaviest box on top within reach: you take two, put the leftover back, and the helper instantly puts the new heaviest on top.
- The obvious way
Sort the list after every smash: O(n² log n).
- The key insight
Put all stones in a max-heap. While at least two remain, pop the two biggest; if they differ, push back the difference. Each pop and push is O(log n).
- The algorithm
- Build a max-heap of all stones (negatives in Python).
- While more than one stone: take the biggest two, call them first and second.
- If first is bigger, push back first - second.
- Return the last stone, or 0 if the heap is empty.
Watch it run
Examplestones = [2, 7, 4, 1, 8, 1]
The two heaviest are 8 and 7. Smash: 8 - 7 = 1 goes back into the pile.
pile: 4, 2, 1, 1, 1
Where people slip
- Python has only a min-heap: negate on the way in and out.
- Handle the empty heap at the end (all stones vanished: answer 0).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
import heapq
def last_stone_weight(stones):
heap = [-weight for weight in stones] # negatives: smallest = heaviest
heapq.heapify(heap)
while len(heap) > 1:
first = -heapq.heappop(heap) # heaviest
second = -heapq.heappop(heap) # next heaviest
if first > second:
heapq.heappush(heap, -(first - second))
return -heap[0] if heap else 0Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.