Repeatedly smash the two heaviest stones until at most one remains, then return its weight.
Problem
You are given an array of stone weights. Repeatedly take the two stones with the largest weights and smash them together.
- If the stones have equal weight, both stones are destroyed.
- If they have different weights, the smaller stone is destroyed and the larger stone's weight becomes the difference.
Continue until there is at most one stone left.
Return the weight of the final stone, or 0 if no stones remain.
Notes
- Each smash operation always uses the two current heaviest stones.
- The order of stones in the input does not matter.
Input Format
- An integer array
stoneswherestones[i]is the weight of the -th stone.
Output Format
- Return a single integer: the weight of the last remaining stone, or
0if all stones are destroyed.
Constraints
1 <= stones.lengthstones[i]are positive integers- Use the two largest stones at each step
Example 1
Input
stones = [2,7,4,1,8,1]
Output
1
Explanation
Take 8 and 7 -> 1 remains: [4,2,1,1,1]. Take 4 and 2 -> 2 remains: [2,1,1,1]. Take 2 and 1 -> 1 remains: [1,1,1]. Take 1 and 1 -> both destroyed: [1]. The last stone weighs 1.
Example 2
Input
stones = [1]
Output
1
Explanation
Only one stone exists, so it is already the final stone.
Show 1 more example
Example 3
Input
stones = [3,3]
Output
0
Explanation
The two heaviest stones have equal weight, so both are destroyed.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.