Last Stone Weight

EasyHeap & Priority QueueArrayHeap

Problem

You have a collection of stones, each with a positive weight. Repeatedly take the two heaviest stones and smash them together: if their weights are equal, both are destroyed; if not, the lighter one is destroyed and the heavier one's weight is reduced by the lighter one's weight. Continue until at most one stone remains, and return its weight, or 0 if none remain.

Example. With stones [2, 7, 4, 1, 8, 1], smashing 8 and 7 leaves a 1, then smashing that new 1 with the existing 4 leaves a 3, then smashing 3 with 2 leaves a 1, and the final smash of 1 and 1 destroys both, leaving weight 0.

Key idea

The process is naturally simulated step by step, but finding the two heaviest stones by scanning the whole collection each round costs O(n) per round. Since the two largest values are needed repeatedly from a collection that keeps changing, this is exactly what a max-heap is built for: it keeps the largest element accessible in constant time and accepts updates cheaply.

Load every stone weight into a max-heap. On each round, pop the two largest weights. If they differ, push the difference back onto the heap as a new stone; if they are equal, push nothing. Repeat until the heap holds zero or one stone, then return the remaining weight or 0. Each round shrinks the heap by one or two stones, so the simulation terminates in at most n rounds.

Solution

// Minimal binary heap; the comparator (hasPriority) decides min-heap or max-heap order.
class Heap<T> {
  private readonly items: T[] = [];

  constructor(private readonly hasPriority: (a: T, b: T) => boolean) {}

  get size(): number {
    return this.items.length;
  }

  push(item: T): void {
    this.items.push(item);
    let i = this.items.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.hasPriority(this.items[parent], this.items[i])) {
        break;
      }
      [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];
      i = parent;
    }
  }

  pop(): T {
    const top = this.items[0];
    const last = this.items.pop()!;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  private bubbleDown(start: number): void {
    let i = start;
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let next = i;
      if (left < this.items.length && this.hasPriority(this.items[left], this.items[next])) {
        next = left;
      }
      if (right < this.items.length && this.hasPriority(this.items[right], this.items[next])) {
        next = right;
      }
      if (next === i) {
        break;
      }
      [this.items[i], this.items[next]] = [this.items[next], this.items[i]];
      i = next;
    }
  }
}

function lastStoneWeight(stones: number[]): number {
  const heap = new Heap<number>((a, b) => a > b); // max-heap: heaviest stone on top
  for (const weight of stones) {
    heap.push(weight);
  }

  while (heap.size > 1) {
    const first = heap.pop();
    const second = heap.pop();
    if (first !== second) {
      heap.push(first - second); // smash: push the leftover weight back as a new stone
    }
  }

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

Complexity

  • Time: O(n log n). Each of up to n rounds does O(1) heap pops and at most one O(log n) push.
  • Space: O(n). The heap holds up to n stone weights.

Watch out for

  • Many languages only provide a min-heap directly; negate weights on insertion, and negate again on removal, to simulate a max-heap.
  • Handle the end state cleanly: return 0 for an empty heap and the stone's weight otherwise.

Pattern

This is a simulation driven by repeatedly needing the current maximum, the signature use case for a heap: whenever "always operate on the current largest or smallest" repeats over changing data, a heap turns each step into a fast, incremental update instead of a full rescan.

Related questions