Last Stone Weight
Part of Practice: Top-K Fundamentals
You are given a list of stones, each with a positive integer weight. Repeatedly take the two heaviest stones and smash them together: if they weigh the same, both are destroyed; if not, the lighter one is destroyed and the heavier one shrinks to the difference of the two weights, going back into the pile.
Keep smashing until at most one stone remains. Return the weight of that final stone, or 0 if none survive. There are at most 30 stones, each weighing between 1 and 1000.
Examples
- Input:
- stones = [2, 7, 4, 1, 8, 1]
- Output:
- 1
Smash 8 and 7 leaving 1 → [2, 4, 1, 1, 1]. Smash 4 and 2 leaving 2 → [2, 1, 1, 1]. Smash 2 and 1 leaving 1 → [1, 1, 1]. Smash 1 and 1 leaving nothing → [1]. The last stone weighs 1.
- Input:
- stones = [1]
- Output:
- 1
Only one stone exists, so it is the answer immediately.
- Input:
- stones = [3, 3]
- Output:
- 0
The two equal stones destroy each other, leaving no stones.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.