Last Stone Weight
Easy · Heap / Priority Queue
You are given a list of positive integers representing the weights of stones. Repeatedly take the two heaviest stones and smash them together: if they are equal, both are destroyed, otherwise the lighter one is destroyed and the heavier one's weight is reduced by the lighter one's weight and it goes back into the pile. Keep doing this until at most one stone remains. Return the weight of the final remaining stone, or 0 if none are left.
Examples
Input: stones = [2,7,4,1,8,1]
Output: 1
Why: Smashing pairs in order of largest weights leaves 8 and 7 -> 1, then 4 and 2 -> 2, then 2 and 1 -> 1, then 1 and 1 -> 0, leaving stone of weight 1.Input: stones = [1]
Output: 1
Why: Only one stone exists so nothing gets smashed and it remains with weight 1.Input: stones = [2,2]
Output: 0
Why: The two equal stones destroy each other completely, leaving no stones.Constraints
1 <= stones.length <= 30, 1 <= stones[i] <= 1000
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Last Stone Weight. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.