Last Stone Weight
Problem
Each turn, smash the two heaviest stones, x ≤ y. If x == y both are destroyed; otherwise a stone of weight y − x remains. Return the weight of the last stone, or 0 if none is left.
Example 1
Input: [2, 7, 4, 1, 8, 1] Output: 1
Test cases
Case 1
Input: [2,7,4,1,8,1] Expected: 1
Case 2
Input: [1] Expected: 1
Case 3
Input: [2,2] Expected: 0
View solutionHide solution1 approach
1. Max-heap simulation
Time O(n log n)Space O(n)
Repeatedly smash the two heaviest; push back the difference if non-zero.
function lastStoneWeight(stones) { const heap = new MinHeap((a, b) => b - a); stones.forEach((s) => heap.push(s)); while (heap.size > 1) { const y = heap.pop(), x = heap.pop(); if (y !== x) heap.push(y - x); } return heap.size ? heap.peek() : 0;}