Last Stone Weight
Easy · Heap & Counting · Array · Heap (Priority Queue) · Simulation
Problem
You are given an array stones, where stones[i] is the weight of a stone. Each turn, take the two heaviest stones, with weights x <= y, and smash them together:
- If x == y, both stones are destroyed.
- Otherwise the lighter stone is destroyed and the heavier one now weighs y - x.
Repeat until at most one stone is left. Return the weight of the remaining stone, or 0 if none remain.
Examples
Input: stones = [5,3,9] Output: 1
Smash 9 and 5 to get 4, then smash 4 and 3 to get 1.
Input: stones = [3,7,2,2] Output: 0
7 and 3 leave 4; 4 and 2 leave 2; the last two 2s destroy each other.
Input: stones = [6] Output: 6
A single stone is never smashed.
Constraints
- 1 <= len(stones) <= 30
- 1 <= stones[i] <= 1000
Approaches
- Sort before every turn — time O(n² log n), space O(n)
Follow-up
What if you could choose any two stones each turn and wanted the smallest possible final weight? Then the order matters and greedy fails: the answer is the smallest difference between two groups the stones can be split into, a subset-sum dynamic program over the total weight.
Related problems
Start free on Cariara · Coding problems · System design studio
