DSA Tracker

Visualize

Last Stone Weight

Max-heap: always smash the two heaviest

time O(n log n)space O(n)

Every round needs the current two heaviest stones, and after a smash the survivor re-enters the pool at an unpredictable rank. Re-sorting the whole pool each round works but wastes effort on stones that never moved. A max-heap keeps exactly what the round needs — the largest value — at the root, and restores that property in O(log n) after each change instead of O(n log n).

Details

Animated on: stones = [2,7,4,1,8,1] — repeatedly smash the two heaviest stones together (equal weights destroy both, otherwise the heavier one survives at weight difference) until at most one remains. Expected: 1.

Problem:Last Stone WeightEasy

Pattern:Heap and Top K

Max-heap: always smash the two heaviest

step 1 / 15

1
7
8
2
1
4

Stones [2, 7, 4, 1, 8, 1] load into an array. Read as a heap it is unordered — slot i's children live at 2i+1 and 2i+2, but nothing yet guarantees a parent outweighs them.

Pseudocode
1FUNCTION lastStoneWeight(stones):
2  BUILD max-heap H from stones
3  WHILE SIZE(H) > 1:
4    a <- EXTRACT-MAX(H)
5    b <- EXTRACT-MAX(H)
6    IF a != b:
7      INSERT(H, a - b)
8  IF SIZE(H) = 1: RETURN H[0]
9  ELSE: RETURN 0

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. Stones [2, 7, 4, 1, 8, 1] load into an array. Read as a heap it is unordered — slot i's children live at 2i+1 and 2i+2, but nothing yet guarantees a parent outweighs them.
  2. heapify sifts every non-leaf down from the middle outward. The heap property now holds everywhere, so the heaviest stone, 8, sits at the root in one O(n) pass — no need to fully sort.
  3. Round 1: pop the root — 8, the heaviest stone left. The last leaf slid into the root and sifted down to restore the heap; 5 stones remain, 7 now on top.
  4. Pop the root again — 7, the second-heaviest. Smashing 8 against 7 leaves a stone of weight 1.
  5. 8 != 7, so the 1-weight survivor goes back in at the next open leaf and sifts up. The heap now holds 5 stones.
  6. Round 2: pop the root — 4, the heaviest stone left. The last leaf slid into the root and sifted down to restore the heap; 4 stones remain, 2 now on top.
  7. Pop the root again — 2, the second-heaviest. Smashing 4 against 2 leaves a stone of weight 2.
  8. 4 != 2, so the 2-weight survivor goes back in at the next open leaf and sifts up. The heap now holds 4 stones.
  9. Round 3: pop the root — 2, the heaviest stone left. The last leaf slid into the root and sifted down to restore the heap; 3 stones remain, 1 now on top.
  10. Pop the root again — 1, the second-heaviest. Smashing 2 against 1 leaves a stone of weight 1.
  11. 2 != 1, so the 1-weight survivor goes back in at the next open leaf and sifts up. The heap now holds 3 stones.
  12. Round 4: pop the root — 1, the heaviest stone left. The last leaf slid into the root and sifted down to restore the heap; 2 stones remain, 1 now on top.
  13. Pop the root again — 1, the second-heaviest. Smashing 1 against 1 leaves a stone of weight 0.
  14. 1 = 1: equal weights destroy each other completely, so nothing returns to the heap. 1 stone remains.
  15. Exactly one stone survives: weight 1. That is the last stone weight.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Last Stone Weight in the editorAll Heap problemsBack to roadmap