The O(n) Club: Last Stone Weight (LeetCode 1046): Who Knew Smash Bros Was a Heap Problem?

The O(n) Club: Last Stone Weight – Who Knew Smash Bros Was a Heap Problem?

⚡ TL;DR

Want to break rocks like a computer-age gladiator? Take the two heaviest stones, smash them together, toss the leftover shard back in the heap (unless they’re a tie—then just sweep the dust under the memory carpet). Keep going until there’s one or zero stones left. Do it all with Java’s max-heap (a.k.a. PriorityQueue with Collections.reverseOrder()), enjoy O(n log n) runtime, and no, you don’t need a gym membership.

// Java max-heap hack!
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for (int stone : stones) heap.add(stone);
while (heap.size() > 1) {
    int y = heap.poll();
    int x = heap.poll();
    if (y != x) heap.add(y - x);
}
return heap.isEmpty() ? 0 : heap.poll();

🧠 How Devs Usually Mess This Up

Step 1: Try brute force. Step 2: Regret. Classic mistakes include:

• The Linear Scan Wasteland: Scanning for the biggest two stones on every turn. It’s O(n²), which means you’ll need more coffee, and your machine needs more patience.
• Forgotten max-heap: Java’s PriorityQueue is a min-heap by default. If you skip Collections.reverseOrder(), you’ll be smashing pebbles, not boulders.
• Zombie Stones: Adding a zero back in when two stones are equal. Please, let the zeros rest.
• NullPointerException Party: Not checking if the heap is empty before polling results in instant crash-and-burn fun.

🔍 What’s Actually Going On

Imagine a gladiator tournament with rocks: the two biggest go head-to-head each round. If they tie, it’s double KO. If not, the leftover chunk goes back for another round. The heap is your MC: it instantly knows who the heaviest contestants are and keeps the brawl moving fast. This is less sorting, more “who gets to lose a chunk next?” Max-heaps handle the drama in O(log n) per battle, so you never have to wait for the popcorn to finish.

🛠️ PseudoCode

• 1. Build a max-heap:

  heap = new PriorityQueue<>(Collections.reverseOrder())
  for stone in stones:
      heap.add(stone)

  Heaviest stone always on top. Just like your favorite muffin.

• 2. Smash until the crowd leaves:

  while (heap.size() > 1):
      y = heap.poll()
      x = heap.poll()
      if y != x:
          heap.add(y - x)

  Remove the top two stones. If they don’t tie, add the “smashed leftovers.” Rinse. Repeat.

• 3. The Last Stone (or None):

  if heap.isEmpty():
      return 0
  else:
      return heap.poll()

  If no stones left, return 0. Otherwise, whatever’s left is your lone survivor.

💻 The Code

import java.util.PriorityQueue;
import java.util.Collections;
 public class LastStoneWeight {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones) heap.add(stone);
        while (heap.size() > 1) {
            int y = heap.poll();
            int x = heap.poll();
            if (y != x) heap.add(y - x);
        }
        return heap.isEmpty() ? 0 : heap.poll();
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Must use a max-heap: Forget Collections.reverseOrder() and you’ll be “smashing” the lightest stones—how inspiring.
• No zombies allowed: If y == x, DON’T put zero back. A zeroton doesn’t belong in your heap.
• Don’t blindly poll: Check heap is non-empty before polling. Otherwise, NullPointerException will make an entrance.
• Performance debrief: Each heap operation = O(log n), total = O(n log n). Quick, neat, no spilled coffee.
• Memory low-key warning: Using the heap costs O(n) space—but if you can’t afford that, I hope you’re not storing cat videos either.

🧠 Interviewer Brain-Tattoo

“If your solution isn’t using a heap, your stones are just collecting dust.”