1046. Last Stone Weight

Each turn, smash the two heaviest stones x ≤ y together: equal stones are both destroyed, otherwise a stone of weight y − x remains. Return the weight of the last stone, or 0 if none remain.

A max-heap hands out the two heaviest stones in O(log n) each round and takes back the leftover just as fast.

1function lastStoneWeight(stones: number[]): number {
2  const heap = new MaxPriorityQueue<number>();
3  for (const s of stones) heap.enqueue(s);
4  while (heap.size() > 1) {
5    const y = heap.dequeue(), x = heap.dequeue();
6    if (y !== x) heap.enqueue(y - x);
7  }
8  return heap.size() ? heap.front() : 0;
9}

max-heap (largest first)

Heapify all stones.

1 / 0

Space: play/pause · ←/→: step