Heap / Priority Queue crash course ↗ · 153

1046. Last Stone Weight

Repeatedly smash the two heaviest stones together — if they differ, the lighter one is destroyed and the difference survives. A max-heap always gives you the two heaviest in O(log n) time, making the whole simulation O(n log n).

● EasyMax-HeapGreedy SimulationTypeScript

PROBLEM What we're solving

You have a pile of stones with weights. Each turn, pick the two heaviest — y ≥ x. If y === x both are destroyed; otherwise the stone of weight y − x remains. Repeat until at most one stone is left and return its weight (or 0 if empty). Example: [2, 7, 4, 1, 8, 1] → smash 8+7 → 1 left → pile is [2, 4, 1, 1, 1] → smash 4+2 → 2 left → [2, 1, 1, 1] → smash 2+1 → 1 → [1, 1, 1] → smash 1+1 → 0 → [1] → answer is 1.

KEY IDEA Always need the two biggest — use a max-heap

Insight → every iteration you need the two heaviest stones at that moment. Sorting once isn't enough because the pile changes each round. A max-heap lets you pop the maximum in O(log n) and push back the remainder in O(log n). That is the entire algorithm — the heap does all the work.

RECIPE Build heap → smash loop → return last

1 · Heapify. Push every stone into a max-heap. This takes O(n) with bottom-up heapify, or O(n log n) with repeated pushes — either is fine here.
2 · Pop twice. Extract the two largest values y and x (y ≥ x). Each pop is O(log n).
3 · Smash. If y !== x, push y − x back. The difference is always positive and smaller than y, so it will not be the next maximum unless everything else is smaller.
4 · Repeat until the heap has 0 or 1 stone. Return heap[0] or 0.

Classic confusion → people forget to check heap.length > 1 in the loop condition and instead check heap.length > 0. That causes an extra iteration where you pop one stone and then try to pop a second from an empty heap — a crash or an incorrect extra call. You need two stones to smash, so loop only while at least two remain.

COST Complexity & alternatives

Sort each round

O(n² log n)

Re-sort up to n times — painful for large inputs.

Max-heap

O(n log n)

Each round does 2 pops + ≤1 push, each O(log n); ≤n rounds.

Space note

The heap holds at most n elements → O(n) extra space. There is no known in-place variant that preserves the same time complexity.

Pattern transfer →this "repeatedly extract two extremes and re-insert a result" pattern appears in Kth Largest Element in a Stream, K Closest Points to Origin, and Merge k Sorted Lists. Whenever a problem asks for repeated access to the maximum (or minimum), reach for a heap.

RUN IT Max-heap: pop two heaviest, push the difference

stones =

step 0 / 13

STARTHeap built from [2, 7, 4, 1, 8, 1]. Max is 8. Begin smashing.

1▶function lastStoneWeight(stones: number[]): number {
2  // Max-heap (simulated with a max-first comparator via a custom MinHeap inverted).
3  // Here we implement a simple binary max-heap inline for clarity.
4▶  const heap: number[] = [];
5 
6  function push(val: number): void {
7    heap.push(val);
8    let i = heap.length - 1;
9    while (i > 0) {
10      const p = (i - 1) >> 1;
11      if (heap[p] >= heap[i]) break;
12      [heap[p], heap[i]] = [heap[i], heap[p]];
13      i = p;
14    }
15  }
16 
17  function pop(): number {
18    const top = heap[0];
19    const last = heap.pop()!;
20    if (heap.length > 0) {
21      heap[0] = last;
22      let i = 0;
23      while (true) {
24        const l = 2 * i + 1, r = 2 * i + 2;
25        let max = i;
26        if (l < heap.length && heap[l] > heap[max]) max = l;
27        if (r < heap.length && heap[r] > heap[max]) max = r;
28        if (max === i) break;
29        [heap[i], heap[max]] = [heap[max], heap[i]];
30        i = max;
31      }
32    }
33    return top;
34  }
35 
36▶  for (const s of stones) push(s);
37 
38  while (heap.length > 1) {
39    const y = pop(); // heaviest
40    const x = pop(); // second heaviest
41    if (y !== x) push(y - x); // leftover fragment
42  }
43 
44  return heap.length === 0 ? 0 : heap[0];
45}

heap (sorted)874211

State

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

heap

size

y (heaviest popped)x (second popped)leftover / resultdestroyed (diff = 0)

slowfast

TYPESCRIPT The solution, annotated

lastStoneWeight.ts
function lastStoneWeight(stones: number[]): number {
  // Max-heap (simulated with a max-first comparator via a custom MinHeap inverted).
  // Here we implement a simple binary max-heap inline for clarity.
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] >= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let max = i;
        if (l < heap.length && heap[l] > heap[max]) max = l;
        if (r < heap.length && heap[r] > heap[max]) max = r;
        if (max === i) break;
        [heap[i], heap[max]] = [heap[max], heap[i]];
        i = max;
      }
    }
    return top;
  }

  for (const s of stones) push(s);

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

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

Reading it block by block

Lines 3–26 — max-heap helpers. A standard binary max-heap: push appends and sifts up; pop swaps the root with the last element, removes it, then sifts the new root down. Both run in O(log n).

Line 28 — build the heap. Inserting each of the n stones one-by-one takes O(n log n). A bottom-up heapify pass would do it in O(n), but for this problem size the difference is negligible.

Lines 30–34 — smash loop. Each iteration pops the two heaviest stones (y ≥ x). If y !== x the fragment y − x is pushed back. The loop guard heap.length > 1 is critical — we need two stones to compare.

Line 36 — final answer. An empty heap means every stone found an equal partner. One stone remaining is the leftover fragment. Return it or 0 accordingly.

Complexity → O(n log n) time: up to n − 1 rounds, each with 2 pops and 1 push at O(log n). O(n) space for the heap array.

INTERVIEWFollow-ups they'll ask

"Return all intermediate stone weights?" Accumulate each y − x result in an array alongside its round number.
"What if you want the minimum remaining weight instead of the last?" Use a min-heap instead; pop the two lightest each round and push x − y if nonzero — mirrors this solution exactly.
"Can you use a different data structure?" A sorted multiset (e.g. a balanced BST) gives the same O(log n) per operation. Sorted array + binary search insert is O(n) per round — worse for large inputs.
"What is the brute-force and why is it worse?" Sorting the array from scratch each round costs O(n log n) per round → O(n² log n) total, vs O(n log n) with a heap.
"Edge cases?" Single stone (stones = [5]) → return 5; all equal ([3, 3, 3, 3]) → all pairs cancel → return 0 or 3 depending on count parity.

OPTIMAL Max-Heap

lastStoneWeight.ts
function lastStoneWeight(stones: number[]): number {
  // Max-heap (simulated with a max-first comparator via a custom MinHeap inverted).
  // Here we implement a simple binary max-heap inline for clarity.
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] >= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let max = i;
        if (l < heap.length && heap[l] > heap[max]) max = l;
        if (r < heap.length && heap[r] > heap[max]) max = r;
        if (max === i) break;
        [heap[i], heap[max]] = [heap[max], heap[i]];
        i = max;
      }
    }
    return top;
  }

  for (const s of stones) push(s);

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

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

Complexity → O(n log n) time: up to n − 1 rounds, each with 2 pops and 1 push at O(log n). O(n) space for the heap array.

ALT 1 Brute force — re-sort each round

O(n² log n) time · O(1) space

Each turn, sort the stones, take the two heaviest off the end, smash them, and push back any leftover — repeating until at most one stone remains.

approach-2.ts
function lastStoneWeight(stones: number[]): number {
  // Mutate the array in place; sort fresh every round to find the two heaviest.
  while (stones.length > 1) {
    stones.sort((a, b) => a - b);
    const y = stones.pop()!;   // heaviest
    const x = stones.pop()!;   // second heaviest
    if (y !== x) stones.push(y - x); // leftover fragment
  }
  return stones.length === 0 ? 0 : stones[0];
}

Note → Up to n rounds, each doing an O(n log n) sort, gives O(n² log n). A max-heap turns each round into two O(log n) pops and one push, for O(n log n) overall.

MNEMONIC The one-liner

"Pop the two heaviest, push the leftover — heap does it all."

TRIGGERS When you see _ → reach for _

"repeatedly pick the two largest/smallest"	max- or min-heap
pile shrinks each round, need running maximum	max-heap pop ×2, push diff
stream of values, need k-th largest at any time	min-heap of size k
merge or combine elements greedily by weight	priority queue simulation

SKELETON The reusable shape

skeleton.ts
const heap: number[] = [];
// push / pop helpers (max-heap)
for (const s of stones) push(s);

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

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

FLASHCARDS Tap to flip

Why use a max-heap instead of sorting each round?

Sorting each round is O(n log n) per iteration → O(n² log n) total. A heap gives O(log n) pop/push, so the whole simulation is O(n log n).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For input [2, 7, 4, 1, 8, 1], what is the correct output?

QUESTION 02

What is the overall time complexity of the max-heap approach?

QUESTION 03

Why must the loop condition be heap.length > 1 and NOT heap.length > 0?

QUESTION 04

What do you return when the heap is empty after the loop?

QUESTION 05

Input [10, 10]: what happens?

QUESTION 06

What data structure alternatives could replace the max-heap with the same per-operation complexity?

QUESTION 07

If the input has an odd number of stones all with the same weight, what is the answer?

QUESTION 08

#1046 · Last Stone WeightSimulate stone smashing with a max-heap: repeatedly extract the two heaviest stones, push their positive difference (if any) back, and return the last remaining weight or 0.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Always need the two biggest — use a max-heap

RECIPE Build heap → smash loop → return last

COST Complexity & alternatives

Space note

RUN IT Max-heap: pop two heaviest, push the difference

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Max-Heap

ALT 1 Brute force — re-sort each round

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _