Last Stone Weight
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Each turn, take the two heaviest stones and smash them together. If they weigh the same both are destroyed; otherwise the lighter is destroyed and the heavier loses that much weight. Return the weight of the last stone left, or 0 if none remain.
Examples
Constraints
- • 1 <= stones.length <= 30
- • 1 <= stones[i] <= 1000
Hints & approach
Hint 1
You repeatedly need the two largest values from a changing collection.
Hint 2
A max-heap gives the largest in O(log n).
Approachtry the hints first
Load all weights into a max-heap (in languages with only a min-heap, store negatives). While more than one stone remains, pop the two largest; if they differ, push their difference back. When the loop ends, return the remaining stone or 0 if the heap is empty. Each round removes at least one stone, so there are at most n rounds.
Time O(n log n) · Space O(n)
