Last Stone Weight

Difficulty: Easy

You have a collection of stones, each with a positive weight. Repeat the following process until at most one stone remains:

Pick up the two heaviest stones (call their weights x and y, with x <= y).
Smash them together. If they're equal weight, both stones are destroyed. Otherwise, the lighter stone is destroyed and the heavier one loses x from its weight, leaving a new stone of weight y - x.

Return the weight of the single stone left at the end, or 0 if every stone was destroyed.

Examples

Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1

Smash 8 & 7 -> 1 remains, leaving [2,4,1,1,1]. Smash 4 & 2 -> 2 remains, leaving [2,1,1,1]. Smash 2 & 1 -> 1 remains, leaving [1,1,1]. Smash 1 & 1 -> both destroyed, leaving [1]. Final answer: 1.

Input: stones = [1]
Output: 1

Only one stone exists to begin with, so nothing gets smashed.

Constraints

1 <= stones.length <= 30
1 <= stones[i] <= 1000

Approach

The process only ever touches the two heaviest stones at each step, so you need repeated fast access to "what's currently the largest value in this collection" - which is exactly what a max-heap provides.

Push every stone's weight onto a max-heap. Then repeatedly pop the two largest values, and if they aren't equal, push the difference back onto the heap. Stop when the heap has one or zero stones left.

Solutions

Brute Force - Re-sort Each Round

Sort the stones every time, smash the two largest, put the result back, and repeat until at most one stone remains.

function lastStoneWeight(stones) {
  const arr = [...stones];

  while (arr.length > 1) {
    arr.sort((a, b) => a - b);
    const y = arr.pop();
    const x = arr.pop();
    if (y !== x) arr.push(y - x);
  }

  return arr.length > 0 ? arr[0] : 0;
}

Time: O(n^2 log n) - up to n rounds, each re-sorting the remaining stones · Space: O(n)

Optimal - Max-Heap

Push all stones onto a max-heap. Repeatedly pop the two heaviest, and if a stone remains after the smash, push it back in.

class MaxHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[i] > this.data[parent]) {
        [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
        i = parent;
      } else break;
    }
  }

  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      const n = this.data.length;
      while (true) {
        let largest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < n && this.data[left] > this.data[largest]) largest = left;
        if (right < n && this.data[right] > this.data[largest]) largest = right;
        if (largest === i) break;
        [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
        i = largest;
      }
    }
    return top;
  }
}

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

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

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

Time: O(n log n) - n stones pushed initially, then O(log n) per pop/push over roughly n rounds · Space: O(n)