LeetCode 1046 · Easy · Heap / Priority Queue

Last Stone Weight

Each turn, smash the two heaviest stones: equal stones both vanish, otherwise the heavier one shrinks by the lighter one's weight. Return the weight of the last stone, or 0.

O(n log n)time
O(n)space
max-heapPriorityQueue on −weights

1–12 weights, each 1 to 99

Smash the two heaviest stones this round

first · y
vs
second · x
→
y − x

stones heap tree shows weights · max at the root

stones list what the PriorityQueue really stores: negated weights, smallest (= heaviest) at index 0

Rounds

public int lastStoneWeight(int[] stones) { List<Integer> list = new ArrayList<>(); for (int s : stones) { list.add(-s); // max-heap trick } PriorityQueue<Integer> heap = new PriorityQueue<>(list); // heapify while (heap.size() > 1) { int first = heap.poll(); // heaviest int second = heap.poll(); // next heaviest if (second > first) { heap.offer(first - second); } } heap.offer(0); return Math.abs(heap.peek());}
first
—
second
—
heap.size()
—
heap
[]

Why it works

  1. Brute force re-sorts: sort, smash the last two, insert the remainder, sort again. O(n² log n), or O(n²) with careful insertion.
  2. A max-heap hands out the heaviest stone in O(log n) and takes a new one back in O(log n). At most n − 1 rounds: O(n log n) overall.
  3. Java's PriorityQueue is a min-heap by default, so store −weight. (A Collections.reverseOrder() comparator also works, but the heapify constructor does not take one.) The most negative value is the heaviest stone, and first - second is the negated remainder, ready to push.
  4. Pitfall: with negatives the comparison flips. second > first means the second stone is lighter, so something is left. Equal stones push nothing.
  5. Line 14: offering 0 makes heap.peek() safe when every stone vanished: on an empty heap it returns null, and unboxing that throws NullPointerException. It replaces a separate empty check.
  6. Related: Kth Largest Element in an Array (LeetCode 215) and K Closest Points (973) use the same PriorityQueue patterns.