DSA problem
Last Stone Weight
You are given an array of integers stones where stones[i] is the weight of the i-th stone. We are playing a game with the stones. On each turn, we choose the two heaviest stones and smash them together. Suppose the heaviest stones have weights x and y with x <= y. The result of the smash is: if x == y both stones are destroyed; if x != y the stone of weight x is destroyed and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone remaining. Return the weight of that stone, or 0 if no stones are left.
The brute-force approach repeatedly scans the array to find the two largest values, swaps and removes them, and inserts the residual back — each round costs O(n), so the total is O(n^2). For a small n that is fine, but a max-heap turns each "find two heaviest" step into O(log n).
The optimal approach builds a max-heap once in O(n), then repeatedly extracts the two largest weights, pushing the absolute difference back when the values differ. The loop runs at most n - 1 times and each operation is O(log n), giving an overall O(n log n) algorithm with O(n) space for the heap itself. The final answer is the heap's root if anything remains, or 0 if the heap is empty.
Examples
stones = [2,7,4,1,8,1]1stones = [1]1stones = [2,2]0Constraints
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.