#1046
Last Stone Weight
Easy Max-heap simulation
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Repeatedly smash the two heaviest stones: equal weights destroy both, otherwise the heavier one loses the lighter one's weight. Return the last stone's weight, or 0.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: keep smashing the two heaviest stones; what's left?
Why this works: a max-heap always hands you the two heaviest.
Example: [2, 7, 4, 1, 8, 1]
8 vs 7 → 1, 4 vs 2 → 2, 2 vs 1 → 1, 1 vs 1 → 0last stone 1
✦Hints open one at a time
You always need the two largest values — a max-heap.
Push back the difference if it's not zero.
↗Approach
Put all stones in a max-heap (Collections.reverseOrder()). While at least two remain, poll two and push back their difference if positive.
</>Solution (Java)
import java.util.*;
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) heap.offer(s);
while (heap.size() > 1) {
int y = heap.poll(), x = heap.poll(); // two heaviest
if (y != x) heap.offer(y - x);
}
return heap.isEmpty() ? 0 : heap.peek();
}
}!Common mistake
Sorting the array again after every smash — O(n² log n).
Complexity
- Time: O(n log n).
- Space: O(n).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon