Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    EasyHeap / Priority Queue

    Last Stone Weight

    You are given an array of integers stones where stones[i] is the weight of the ith stone.

    We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is: if x == y, both stones are destroyed; if x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

    At the end of the game, there is at most one stone left. Return the weight of the last remaining stone. If there are no stones left, return 0.

    Example 1

    Input: stones = [2,7,4,1,8,1]

    Output: 1

    Explanation: Combine 7 and 8 to get 1: [2,4,1,1,1]. Combine 2 and 4 to get 2: [2,1,1,1]. Combine 2 and 1 to get 1: [1,1,1]. Combine 1 and 1 to get 0: [1]. That last stone weighs 1.

    Example 2

    Input: stones = [1]

    Output: 1

    Constraints

    • 1 <= stones.length <= 30
    • 1 <= stones[i] <= 1000
    View original on LeetCode ↗

    Every round we need the two heaviest stones. Repeatedly scanning for the max is wasteful; a max-heap gives the current heaviest stone in O(log n) and stays balanced as we remove and reinsert. Python’s heapq is a min-heap, so we store negated weights to simulate a max-heap.

    Sort Every Round

    Time O(n² log n)Space O(n)

    Sort the stones descending, smash the top two, put the leftover back in, and repeat.

    class Solution:
        def lastStoneWeight(self, stones: list[int]) -> int:
            stones = stones[:]
            while len(stones) > 1:
                stones.sort(reverse=True)
                y = stones.pop(0)
                x = stones.pop(0)
                if y != x:
                    stones.append(y - x)
            return stones[0] if stones else 0

    Why it’s slow: re-sorting the entire list every round is massive overkill just to find two elements. With up to n rounds, each doing an O(n log n) sort, this is O(n² log n).

    Max-Heap

    OptimalTime O(n log n)Space O(n)

    Push every stone’s negated weight into a heap so the largest weight sits at the root (as the smallest negative). Each round: pop the two largest, and if they differ, push the difference back in. Stop when at most one stone remains.

    import heapq
    

    class Solution:
        def lastStoneWeight(self, stones: list[int]) -> int:
            heap = [-s for s in stones]
            heapq.heapify(heap)
            while len(heap) > 1:
                y = -heapq.heappop(heap)
                x = -heapq.heappop(heap)
                if y != x:
                    heapq.heappush(heap, -(y - x))
            return -heap[0] if heap else 0

    Tracing stones = [2, 7, 4, 1, 8, 1] (array shown as positive weights; the heap itself stores negatives, with the heaviest stone always at index 0):

    Watch how each pop moves the last stone to the root and sifts it down, so the heaviest remaining stone always rises back to index 0.

    Heap array

    input
    root
    2
    0
    7
    1
    4
    2
    1
    3
    8
    4
    1
    5
    y (heaviest)—
    x—
    y - x—
    stones left6
    1 / 14
    currentcomparingresult

    Start: six stones. Python heapq is a min-heap, so each weight is stored negated. The heaviest stone becomes the smallest key.

    Correctness: the heap always exposes the current two heaviest stones at the cost of a pop each, and pushing the smashed remainder maintains the invariant for the next round. This exactly simulates the rules of the game.

    Complexity: up to n rounds, each doing 2 pops and at most 1 push, all O(log n) on a heap of size at most n → O(n log n) total. Space is O(n) for the heap.

    More Heap / Priority Queue practice