Last Stone Weight

You have an array of stone weights. The machine repeatedly takes the two heaviest stones and smashes them together: if they weigh the same, both are destroyed; if not, the heavier stone's remainder (difference) goes back into the pile. Repeat until at most one stone is left, and return its weight, or 0 if none remain.

The key insight: the operation always touches the two largest elements, and after the smash a new, smaller stone may be reinserted. A sorted list would need O(n) insertion per smash; a max-heap keeps both "find the two heaviest" and reinsertion at O(log n). In Python, negate the values so the min-heap acts as a max-heap.

Approach in steps:

1. Heapify all weights as negatives.
2. Pop the two largest; if they differ, push back the difference (negated).
3. When fewer than two stones remain, return the survivor's weight, or 0 for an empty pile.

import heapq
 
def lastStoneWeight(stones):
    heap = [-w for w 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

Time is O(n log n) — n heapifies plus at most n pops and pushes; space is O(n).

Trickiest edge case: a single stone. With [1], the loop never runs and the machine must return 1, not crash on a second pop. The equal-weights case matters too: [3,3] smashes to nothing, the heap ends empty, and the answer is 0 — guard the final read against an empty heap.