Last Stone Weight Solutions & Complexity

1. Define the problem

Last Stone Weight

You are given an array of integers stones, where each value is the weight of a stone. Repeat this process while more than one stone remains: take the two heaviest stones, with weights x and y where x ≤ y. If x === y, both stones are totally destroyed. Otherwise, the stone with weight x is destroyed and the stone with weight y has new weight y - x. Return the weight of the last remaining stone, or 0 if none remain. Use a max-heap so the two heaviest stones are always O(log n) to find and remove.

Constraints

1 ≤ stones.length ≤ 30
1 ≤ stones_i ≤ 1000

Example

Inputstones = [2, 7, 4, 1, 8, 1]

Output1

Explanation 8 and 7 smash to 1 → [2, 4, 1, 1, 1]. 4 and 2 smash to 2 → [2, 1, 1, 1]. 2 and 1 smash to 1 → [1, 1, 1]. 1 and 1 destroy each other → [1]. Answer: 1.

2. Visualize the solution

Pop the two heaviest, push back the difference

i08

i17

i24

i32

i41

i51

Statusinit

Max-heap built from [2, 7, 4, 1, 8, 1]. Two heaviest: 8 and 7.

What happens in this step

heapify [2, 7, 4, 1, 8, 1]
heap (max-heap) ~ [8, 7, 4, 2, 1, 1]

Sifting down from the last parent up to the root rebuilds the list so every parent is ≥ its children. The root, 8, and its next-largest sibling, 7, are the two heaviest stones.

Step 1 of 4

Steps to visualize

Build a max-heap from every stone weight.
Pop the two heaviest stones, y and x.
If they differ, push the difference y - x back onto the heap.
Repeat until at most one stone remains.
The row is the heap array. A slot marked — is empty because the heap shrank.
The last stone (or 0 if none) is the answer.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Pop the two heaviest, push back the difference

i08

i17

i24

i32

i41

i51

Statusinit

Max-heap built from [2, 7, 4, 1, 8, 1]. Two heaviest: 8 and 7.

What happens in this step

heapify [2, 7, 4, 1, 8, 1]
heap (max-heap) ~ [8, 7, 4, 2, 1, 1]

Sifting down from the last parent up to the root rebuilds the list so every parent is ≥ its children. The root, 8, and its next-largest sibling, 7, are the two heaviest stones.

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function lastStoneWeight(stones) {
  const heap = stones.slice();

  function siftDown(i) {
    const size = heap.length;
    while (true) {
      let largest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left] > heap[largest]) largest = left;
      if (right < size && heap[right] > heap[largest]) largest = right;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
  }

  function heapify() {
    for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i--) siftDown(i);
  }

  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      siftDown(0);
    }
    return top;
  }

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

  heapify();

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

  return heap.length ? heap[0] : 0;
}

Time: O(n log n)
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`stones = [2, 7, 4, 1, 8, 1]`	`1`	example from the docstring
`stones = [1, 1, 1, 1]`	`0`	every stone pairs off and destroys evenly, nothing left
`stones = [5]`	`5`	smallest valid input, no smashing at all
`stones = [3, 3]`	`0`	two equal stones destroy each other completely
`stones = [10, 4]`	`6`	two differing stones leave a remainder
`stones = []`	`0`	no stones at all
`stones = [9, 7, 5, 3]`	`0`	a longer chain of smashes that fully cancels out

Last Stone Weight