1046. Last Stone Weight

Quick Identifier

Topic: heap-priority-queue
Pattern: Top-K / Heap (max-heap)
Difficulty: Easy
Companies: Google, Amazon, Microsoft, Apple, Meta
Frequency: High
LeetCode: 1046

Quick Sights

Time Complexity: O(n log n) from the optimal approach.
Space Complexity: O(n) from the optimal approach.
Core Mechanism: Repeatedly take the two heaviest stones, smash them (replace with difference or remove both if equal) until at most one stone remains. Return that stone's weight, or 0 if none.

Concept Explanation

Repeatedly take the two heaviest stones, smash them (replace with difference or remove both if equal) until at most one stone remains. Return that stone's weight, or 0 if none.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Always pick two largest each round
Simulate process with evolving multiset
"Heaviest" → priority queue / max-heap

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — sort each round — O(n^2 log n) — wasteful.
Better — multiset / balanced BST — O(n log n) total possible.
Optimal — max-heap pull two, push diff — O(n log n) time, O(n) space.

Optimal Solution

Go

import (
	"container/heap"
)

type IntMaxHeap []int

func (heapSlice IntMaxHeap) Len() int { return len(heapSlice) }
func (heapSlice IntMaxHeap) Less(left, right int) bool {
	return heapSlice[left] > heapSlice[right]
}
func (heapSlice IntMaxHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *IntMaxHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(int))
}

func (heapSlice *IntMaxHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	value := old[length-1]
	*heapSlice = old[0 : length-1]
	return value
}

func lastStoneWeight(stones []int) int {
	maxHeap := &IntMaxHeap{}
	heap.Init(maxHeap)
	for _, weight := range stones {
		heap.Push(maxHeap, weight)
	}
	for maxHeap.Len() > 1 {
		first := heap.Pop(maxHeap).(int)
		second := heap.Pop(maxHeap).(int)
		if first != second {
			heap.Push(maxHeap, first-second)
		}
	}
	if maxHeap.Len() == 0 {
		return 0
	}
	return (*maxHeap)[0]
}

JavaScript

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

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

  push(value) {
    this.data.push(value);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index] <= this.data[parentIndex]) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let largest = index;
      if (leftChild < length && this.data[leftChild] > this.data[largest]) {
        largest = leftChild;
      }
      if (rightChild < length && this.data[rightChild] > this.data[largest]) {
        largest = rightChild;
      }
      if (largest === index) {
        break;
      }
      this.swap(index, largest);
      index = largest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function lastStoneWeight(stones) {
  const maxHeap = new MaxHeap();
  for (const weight of stones) {
    maxHeap.push(weight);
  }
  while (maxHeap.size() > 1) {
    const first = maxHeap.pop();
    const second = maxHeap.pop();
    if (first !== second) {
      maxHeap.push(first - second);
    }
  }
  return maxHeap.size() === 0 ? 0 : maxHeap.pop();
}

Walkthrough

stones = [2, 7, 4, 1, 8, 1].

step	pop order	result push	remaining conceptual
1	8, 7	1	..., 2,4,1,1,1
2	4, 2	2	..., 1,1,1,2
...	continues	until one or zero

Invariant: Heap always holds current stone weights; each step removes the two global maxima.

Edge Cases

Single stone → return it
Two equal stones → both vanish → 0
All zeros (if allowed) → 0

Pitfalls

Using min-heap without negation → wrong order
Subtracting in wrong order — problem says two heaviest smashed; first - second when first >= second after pops from max-heap

Variants

Last stone weight II (multiple rounds / game theory) — different objective
Use sorting each step — same asymptotic with simpler code for tiny n

Mind-Map Tags

#heap #max-heap #simulation #greedy #two-largest