Last Stone Weight

Last Stone Weight is the cleanest introduction to the heap (priority queue). It teaches the move that powers a whole family of problems: when you keep needing the largest (or smallest) thing in a changing collection, reach for a heap.

The slow way first

The naive plan: each round, sort the list, take the last two, smash, and put the result back. Sorting is O(n log n) per round, and there are up to n rounds, so the whole thing is O(n² log n).

The question to ask: I never need the list fully sorted — I only ever need the two largest. Re-sorting everything just to read off the top is wasteful. A structure that hands me the maximum cheaply and lets me insert cheaply is exactly a heap.

The idea: a max-heap of weights

Put every stone in a max-heap, so the heaviest is always at the root. Each round, pop twice to get the two heaviest stones in O(log n). Smash them; if they differ, push the difference back, also O(log n). Repeat until one stone (or none) is left.

Python only ships a min-heap (heapq), so the standard trick is to store negated weights: the most-negative value sits at the root, which is the largest original weight. Negate again on the way out.

Walk through it

Step through the animation. Start with the heap [8, 7, 4, 1, 2, 1]. Round 1 pops 8 and 7 → push 1. Round 2 pops 4 and 2 → push 2. Round 3 pops 2 and 1 → push 1. Round 4 pops 1 and 1 — equal, so both vanish and nothing is pushed. One stone of weight 1 is left, so the answer is 1. Watch the tree shrink one node per round.

Pseudocode

build a max-heap from all stone weights
while the heap has more than one stone:
    a = pop the largest
    b = pop the next largest
    if a != b:
        push (a - b) back onto the heap   # heavier stone, shrunk
if the heap is empty: return 0
otherwise return the one remaining weight

The Python solution

def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = -heapq.heappop(heap)
        b = -heapq.heappop(heap)
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

• We store negated weights so Python min-heap behaves as a max-heap — the smallest stored value is the largest real weight.
• heapq.heapify turns the list into a valid heap in O(n), in place.
• Each heappop removes and returns the root (the heaviest stone) in O(log n); we negate it back to a positive weight.
• If the two stones differ, we push -(a - b) — the negated leftover weight — so it rejoins the heap in the right spot.
• At the end, an empty heap means every stone was destroyed (return 0); otherwise -heap[0] is the last stone weight.

Complexity

There are at most n rounds, and each does a constant number of O(log n) heap operations, giving O(n log n) overall. The heap itself is the O(n) extra space.

When this pattern shows up

Practice