Smash the two heaviest rocks until one is left

Heaps and priority queues Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
import heapq
rocks = [-w for w in [2, 7, 4, 1, 8, 1]]
heapq.heapify(rocks)
while len(rocks) > 1:
    a, b = -heapq.heappop(rocks), -heapq.heappop(rocks)
    if a != b:
        heapq.heappush(rocks, -(a - b))
print(-rocks[0] if rocks else 0)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 1

Right: 8-7 leaves 1, 4-2 leaves 2, 2-1 leaves 1, and 1-1 leaves the final 1.

A heap turns each 'find the two heaviest' into two O(log n) pops instead of a fresh sort.

Why not the others?
  • B 0. One rock of weight 1 survives.
  • C 2. The 2 left after 4-2 is later smashed against a 1.

30-second answer

A max-heap gives the two heaviest in O(log n) each. Push the difference back when it is non-zero. Each smash removes at least one rock, so there are at most n rounds: O(n log n) time, with O(n) space for the heap.

Practise saying it · 30 s. No recording, just a timer

Explain the rock-smashing simulation.

Say your answer out loud, then check which of these points you covered:

  • Max-heap
  • Push back the difference
  • O(n log n)

Deep dive

Python needs negated weights for a max-heap.

Sorting after every smash is O(n² log n).

It is a simulation; the heap just makes 'take the biggest' cheap.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from heapq import heapify, heappop, heappush


def last_rock(rocks: list[int]) -> int:
    pile = [-w for w in rocks]  # max-heap by negation
    heapify(pile)
    while len(pile) > 1:
        heavy, next_heavy = -heappop(pile), -heappop(pile)
        if heavy > next_heavy:
            heappush(pile, next_heavy - heavy)
    return -pile[0] if pile else 0

Common mistakes

  • Pushing a zero difference back, which is harmless but wasteful.
  • Forgetting the empty result.

Senior take & follow-ups

Point out that each round removes a rock, which bounds the loop.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if the goal is the smallest possible last weight with free choice of pairs?

    Show hint

    That becomes a subset-sum problem: split rocks into two groups with the closest totals.

  2. Can you avoid the heap?

    Show hint

    With small weights, a count array scanned from the top works.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.