Last Stone Weight

The process is a simulation. Take the two heaviest stones, smash them together, and if they are different the difference becomes a new stone that goes back into the collection. If they are equal, both disappear. Continue until at most one stone is left, and its weight is the answer. If no stones remain, the answer is zero.

What the problem is really asking is what the smallest possible remaining weight is. The greedy choice to always smash the two heaviest is optimal, and the intuition is that the heaviest stones are the ones most likely to cancel each other out, leaving smaller residues behind.

The mechanism is that each round you need the two largest elements. Doing that by scanning the whole collection every time is quadratic, so the natural implementation keeps the stones in a max heap and takes the two roots.

The trade-off to name is that the greedy argument is not a full proof, and a careful interviewer may push on it. The standard justification is an exchange argument: if an optimal sequence smashed a lighter pair before a heavier one, you can swap those two rounds without making the outcome worse, because the heavier difference dominates the lighter one. That is the sort of reasoning an interviewer wants to hear. The other point is the complexity, which is quadratic if you scan the list each round and linear in the number of rounds times the logarithm of the number of stones if you use a heap.

Keep the stones in a max heap, take the two heaviest each round, and push back the difference when they are not equal.

import heapq


def last_stone_weight(stones):
    heap = [-stone for stone 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


print(last_stone_weight([2, 7, 4, 1, 8, 1]))
print(last_stone_weight([1, 2]))

The outputs are 1 and 1. In the first case eight and seven smash to leave one, four and two smash to leave two, two and one leave one, and the two ones cancel, so a single stone of weight one remains.

The mechanism is that the negated values turn Python's min heap into a max heap, so the two heaviest stones are the two roots and the rest of the heap is untouched. Each round costs two pops and at most one push, all logarithmic.

The trade-off to name is that the heap is not necessary for small inputs, and the simple version that repeatedly scans for the two largest is easier to read. The heap version matters when the number of stones is large, because the number of rounds can be proportional to the number of stones and each scan is linear. There is also a subtlety with equal stones: when the two heaviest are equal they cancel completely and nothing is pushed back, which is why the difference check is inside the loop rather than always pushing.