DSAPrep
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):

8
0
7
1
4
2
1
3
2
4
1
5
1 / 10
comparingresultcurrent

heapify: root is the heaviest stone, 8.

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.