What it teaches: A max-heap as a simulation tool: repeatedly take the two largest.
Practise it on judges as “Last Stone Weight”.
The problem
Each turn, smash the two heaviest stones x ≤ y together: if equal, both are destroyed; otherwise a stone of weight y − x remains. Return the weight of the last stone, or 0 if none remain.
Example 1
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Constraints
1 ≤ n ≤ 30
1 ≤ stone ≤ 1000
Pattern clues in the wording
→ Repeatedly take the largest items
These clues point to Top K with a Heap: Keep a heap of size k: a min-heap for the k largest, a max-heap for the k smallest.
Stuck? Take one hint at a time
Solution.java · starter
import java.util.*;
class Solution {
public int lastStoneWeight(int[] stones) {
return 0;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Put all stones in a max-heap. While at least two remain, poll two and push back the difference if it's non-zero.
Approach 1
import java.util.*;
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
for (int s : stones) pq.offer(s);
while (pq.size() > 1) {
int y = pq.poll(), x = pq.poll();
if (y != x) pq.offer(y - x);
}
return pq.isEmpty() ? 0 : pq.peek();
}
}
Verdict: Direct simulation.
Before you submit
Edge cases and common mistakes
Test these inputs
One stone
All stones destroyed
Mistakes people make
Re-sorting the array every turn (O(n² log n)).
Interview
Follow-up questions
What if you can choose any two stones each turn and want the smallest possible final weight?