Last Stone Weight

Description

Repeatedly smash the two heaviest positive-weight stones. Equal stones disappear; otherwise their positive difference returns to the pile. Return the final weight, or zero if none remain.

Solution

import heapq

def last_stone_weight(stones):
    heap = [-value for value in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        first, second = -heapq.heappop(heap), -heapq.heappop(heap)
        if first != second:
            heapq.heappush(heap, second - first)
    return -heap[0] if heap else 0

Examples

Approach

Use a max-priority queue to obtain the two largest stones. Push their difference if nonzero and continue until at most one stone remains. Python and Go use negated values in a min-heap.