Last Stone Weight

Problem

You have a pile of stones with given weights. Repeatedly smash the two heaviest together: if they're equal both vanish, otherwise the lighter is destroyed and the heavier survives with its weight reduced by the lighter's. Keep going until at most one stone remains — return its weight, or 0 if none.

Your signal — what pointed here?Your skeleton — the reusable shape

Signal

"Repeatedly grab the two current largest, combine, put the result back" is a direct max-heap simulation — every step needs the current max and second-max, which is exactly what a heap gives you in O(log n) instead of re-scanning.

Approach

Push all weights onto a max-heap (Python's heapq is min-heap only, so negate on the way in and out). Pop the two largest, and if they differ, push the difference back. Repeat until at most one stone is left.

Skeleton

heap = [-w for w in stones]; heapify(heap)
while len(heap) > 1:
    a, b = -pop(), -pop()
    if a != b: push(-(a - b))
return -heap[0] if heap else 0

Solution

import heapq

def last_stone_weight(stones: list[int]) -> int:
    heap = [-w for w in stones]
    heapq.heapify(heap)

    while len(heap) > 1:
        first = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if first != second:
            heapq.heappush(heap, -(first - second))

    return -heap[0] if heap else 0

Complexity

O(n log n) time — n smashes in the worst case, each a constant number of O(log n) heap operations. O(n) space for the heap.

Pitfalls

Forgetting to negate on both push and pop — Python's heap is always a min-heap, so every value you store has to be negated consistently.
Sorting the whole list after every smash also works but is O(n² log n) overall — the heap avoids re-sorting on each step.
Not handling the empty-heap case at the end (all stones cancelled out exactly) — return 0, not heap[0] on an empty heap.