Last Stone Weight

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}