Last Stone Weight

Repeated sorting — rebuild the arena every round

Keep a working copy of the weights. Sort it, remove the two largest values, and return their difference to the list when that difference is nonzero.

def last_stone_weight(stones: list[int]) -> int:
    arena = stones[:]
    while len(arena) > 1:
        arena.sort()
        heavier = arena.pop()
        lighter = arena.pop()
        if heavier != lighter:
            arena.append(heavier - lighter)
    return arena[0] if arena else 0

The code mirrors the game exactly, which makes it a useful correctness baseline. Its cost is the repeated sorting: almost the same list may be sorted again after every collision.

Time O(n² log n), space O(n) for the working copy.

Max-heap simulation — keep the heaviest ready

A max-heap keeps the current largest value at its root. Python's standard heap is a min-heap, so store each weight as a negative number: the most negative entry represents the heaviest stone.

import heapq
 
 
def last_stone_weight(stones: list[int]) -> int:
    arena = [-weight for weight in stones]
    heapq.heapify(arena)
 
    while len(arena) > 1:
        heavier = -heapq.heappop(arena)
        lighter = -heapq.heappop(arena)
        if heavier != lighter:
            heapq.heappush(arena, -(heavier - lighter))
 
    return -arena[0] if arena else 0

Every round performs two removals and at most one insertion. There are at most n - 1 rounds because each collision reduces the number of stones by at least one.

Time O(n log n), space O(n) for the heap.