A packing line weighs outbound crates. When two collide at the merge, both leave the belt unless one is heavier — then a remainder crate of weight |a - b| goes back on the pile. The intern version sorted the whole pile after every smash. A dozen crates were instant. A few thousand on the night wave were still sorting when the belt jammed.

Last Stone Weight asks for the leftover after repeatedly smashing the two heaviest. A heap already gives the next-best at the root. Sorting the pile uses that answer and still pays a full sort per smash.

This is an interview writeup, not a heap lecture. That post owns sift. Java’s PriorityQueue is a min-heap. Here we invert it so poll is the heaviest, then offer the remainder if the smash was unequal. Same next-best-at-the-root as Kth Largest in a Stream: that post keeps k winners so peek is the floor. This one repeatedly extracts the two heaviest.

The problem

Given an int[] stones of positive weights, smash the two heaviest until one or zero stones remain. Equal weights both vanish. Unequal leaves a stone of weight |a - b|. Return the last weight, or 0 if the pile is empty.

stones = [3, 9, 5, 16, 7]  →  2
stones = [11, 4, 11]       →  4
stones = [8, 8]            →  0

First row: 16 vs 9 leaves 7; then 7 vs 7 both gone; 5 vs 3 leaves 2. Second: the two 11s cancel, 4 sits. Third: equal smash, empty pile.

Note: One stone already is a valid input — return it. Do not smash a singleton against air.

Sort after every smash is the honest brute force

Copy into a list. While two or more remain, sort, pull the last two (now the heaviest), and put a - b back if nonzero. After a sort, a >= b, so the abs is just the difference. Correct. Slow in the smash count.

int lastStoneWeightSort(int[] stones) {
    List<Integer> pile = new ArrayList<>();
    for (int s : stones) {
        pile.add(s);
    }
    while (pile.size() > 1) {
        Collections.sort(pile);
        int a = pile.remove(pile.size() - 1);
        int b = pile.remove(pile.size() - 1);
        if (a != b) {
            pile.add(a - b);
        }
    }
    return pile.isEmpty() ? 0 : pile.get(0);
}

At a dozen stones this is a rounding error. At a few thousand you paid a full sort per smash for a question a max-heap answers with two polls: what are the two heaviest right now?

Max-heap: poll two, offer the remainder if nonzero

PriorityQueue is a min-heap. Root is the lightest resident. Pass Collections.reverseOrder() (or a comparator that flips natural order) so the root is the heaviest. Say the invert out loud.

  • Offer every stone.
  • While two or more remain, poll twice. The first poll is heavier, so a - b is the remainder.
  • If they differ, offer that difference. Equals vanish with no offer.
  • Return peek, or 0 if the heap is empty.

You never sort the pile. A remainder is just another stone.

stones = [3, 9, 5, 16, 7]
max-heap (root heaviest): 16, 9, 7, 5, 3

poll 16, poll 9   diff 7   offer 7     7, 7, 5, 3
poll 7,  poll 7   equal    no offer    5, 3
poll 5,  poll 3   diff 2   offer 2     2
one left                               → 2

The Java is that walk. Reverse order is the only trick:

int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    for (int s : stones) {
        heap.offer(s);
    }
    while (heap.size() > 1) {
        int a = heap.poll();
        int b = heap.poll();
        if (a != b) {
            heap.offer(a - b);
        }
    }
    return heap.isEmpty() ? 0 : heap.peek();
}

Time is O(n log n) — n offers, then at most n − 1 smashes of two polls and maybe one offer. Space is O(n) for the heap. Do not re-lecture sift at the whiteboard unless they ask.

Note: A natural-order PriorityQueue polls the two lightest. The leftover is still a legal smash of some pair, not the heaviest pair the prompt named. Invert the comparator, or you solved a different game.

What interviewers usually poke next

  • Already one stone. Return it. The while loop never runs. Empty input is usually out of contract; ask, then 0.
  • Every smash equals. The heap drains to empty; return 0. [8, 8] is the smallest case. A longer pile can cancel the same way.
  • Two equal heaviest, others remain. Poll both, skip the offer, continue. Do not insert a zero — a zero stone is a ghost smash next turn.
  • Why brute is O(n² log n). Up to n − 1 smashes, each a full sort of a pile that stays Θ(n) for a long stretch. Heap pays O(log n) per offer/poll, so O(n log n) total.
  • Min-heap by accident. Same code, no reverse order: you smash the two lightest. Say you inverted, and why.
  • One-shot kth largest. A frozen array that asks for the kth largest is a different prompt. This one mutates the pile. Do not solve it here.

You are done with this problem when you can say, out loud, why sorting after every smash is correct, why a reversed PriorityQueue peeks the heaviest, and why a min-heap solves a different smash.