Last Stone Weight

Problem

Each turn, take the two heaviest stones and smash them. If equal, both destroyed; if unequal, larger stone remains with weight difference. Return the weight of the last stone or 0.

Key insight: Max-heap. Repeatedly extract top two, push difference if non-zero.

Solutions

// C — use negated min-heap array

// C++
int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> maxH(stones.begin(), stones.end());
    while (maxH.size() > 1) {
        int a = maxH.top(); maxH.pop();
        int b = maxH.top(); maxH.pop();
        if (a != b) maxH.push(a - b);
    }
    return maxH.empty() ? 0 : maxH.top();
}

// Java
public int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
    for (int s : stones) maxH.offer(s);
    while (maxH.size() > 1) {
        int a = maxH.poll(), b = maxH.poll();
        if (a != b) maxH.offer(a - b);
    }
    return maxH.isEmpty() ? 0 : maxH.peek();
}

// JavaScript
function lastStoneWeight(stones) {
    // Simple simulation with sorting (for small inputs)
    stones = [...stones].sort((a, b) => a - b);
    while (stones.length > 1) {
        const a = stones.pop(), b = stones.pop();
        if (a !== b) {
            let pos = stones.findIndex(x => x >= a - b);
            if (pos === -1) stones.push(a - b);
            else stones.splice(pos, 0, a - b);
        }
    }
    return stones.length ? stones[0] : 0;
}

# Python
import heapq

def lastStoneWeight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = -heapq.heappop(heap)
        b = -heapq.heappop(heap)
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

Complexity

Time: O(n log n)
Space: O(n)