Typorithm · medium

Last Stone Weight

last-stone-weightheapsmax-heapsimulationgreedy

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Last Stone Weight

Heaps

Repeatedly smash the two heaviest stones from a max-heap, returning the remainder until at most one remains.

Each round must find the two heaviest stones, exactly what a max-heap gives in O(log n).

Smashing two equal stones destroys both; unequal stones leave their difference, pushed back in.

The simulation ends with one stone (the answer) or none (zero).

Max-heap yields the two heaviest.

Push back the weight difference.

Stop when one or zero remain.

function lastStoneWeight(stones) {
  const heap = new MaxHeap();
  for (const stone of stones) {
    heap.push(stone);
  }

  while (heap.size() > 1) {
    const heaviest = heap.pop();
    const second = heap.pop();
    if (heaviest !== second) {
      heap.push(heaviest - second);
    }
  }

  return heap.size() === 1 ? heap.pop() : 0;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Max-heap

A max-heap surfaces the two heaviest stones each round.

const heap = new MaxHeap()

2. Pop heaviest

Extract the largest, then the next largest.

const heaviest = heap.pop()

3. Smash remainder

Unequal stones leave a remainder that goes back in.

if (heaviest !== second) {
      heap.push(heaviest - second);
    }

4. Final stone

One stone left is the answer; none means zero.

return heap.size() === 1 ? heap.pop() : 0

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.