You have a pile of stones, and stones[i] is the weight of one of them. Each turn, take the two
heaviest stones, weighing x and y with 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. It goes back in the pile.
Keep going until at most one stone is left. Return its weight, or 0 if no stone is left.
Example 1
- Input
- stones = [6, 3, 10, 2]
- Output
- 1
Example 2
- Input
- stones = [3, 9, 4, 2, 8]
- Output
- 0
Constraints
stonesholds 1 to 1000 weights.- Every weight is between 1 and 1000.
Show the pattern
Heap
Every turn needs the two heaviest stones, and a smash can put a new stone back in the pile. A max-heap hands over the heaviest item again and again while the pile keeps changing.
See heap in a visualiserShow the approach
Put every weight in a max-heap. While it holds at least two stones, pop the heaviest, y, and the
next heaviest, x; if they differ, push y − x back. Each turn removes at least one stone, so
there are fewer than n turns, each costing O(log n). At the end, return the remaining stone's
weight, or 0 if the heap is empty.
Time: O(n log n) · Space: O(n)