Heap · LC #1046
Last Stone Weight
Use a max-heap to repeatedly extract the two heaviest stones, smash them, and push the remainder back until one or zero stones remain.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Stones smash: take the two heaviest; if equal, both destroyed; else the heavier becomes `heavy - light`. Return the last stone's weight or 0.
Sample I/O
Input: stones=[2,7,4,1,8,1] Output: 1 Input: stones=[1] Output: 1
Intuition
How to Think About It
Intuition
We always smash the two largest - a max-heap gives O(log n) access to the current maximum. The simulation is straightforward: pop twice, push difference if non-zero, repeat.
Core Concept
Build a max-heap from stones. While size > 1: pop a (largest) and b (second largest). If a != b push a-b. Return heap[0] or 0 if empty. Time O(n log n), Space O(n).
When to use
Simulation problems that repeatedly need the current maximum (or minimum); priority-based processing queues.
When NOT to use
When you only need the final count, not the exact weights (may have a mathematical shortcut); when n is tiny (just sort repeatedly).
Key Insights
What to Know Cold
- Max-heap provides O(log n) extract-max - essential for repeated maximums.
- Python's heapq is a min-heap - negate values to simulate max-heap.
- Push back a-b (not b-a) since a >= b after two pops.
- Return 0 when heap is empty - all stones annihilated each other.
- Each smash reduces stone count by at least 1 → at most n-1 smashes → O(n log n) total.
1 example
Worked Examples
Smash stones until one remains
stones=[2,7,4,1,8,1], repeatedly smash two heaviest.
Max-heap simulation.
Output: 1
Introduces max-heap simulation pattern used in Task Scheduler, Reorganize String, and process scheduling problems.