Last Stone Weight
The key idea
You always need the two heaviest stones each turn, and after a smash the new (possibly smaller) stone must rejoin the contenders. A max-heap gives you both the heaviest in O(log n) and lets you push the remainder back, so you never re-sort the whole pile.
Problem
You are given an array of integers stones where stones[i] is the weight of the i-th stone.
Each turn, choose the two heaviest stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of the smash is:
- If x == y, both stones are destroyed.
- If x != y, the stone of weight x is destroyed and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left. Return the weight of the last remaining stone, or 0 if there are no stones left.
Constraints
1 <= stones.length <= 301 <= stones[i] <= 1000
Examples
Input: stones = [2,7,4,1,8,1]
Output: 1
Input: stones = [1]
Output: 1
Complexity
Time: O(n log n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM