Easy·[2026-03-27]

1046. Last Stone Weight

[#heap]

## description

## 1046. 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, and
–
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:

plain text

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

plain text

Input: stones = [1]
Output: 1

–
1 <= stones.length <= 30
–
1 <= stones[i] <= 1000

Constraints:

## notes

### Intuition

We want to grab the two largest stones on every iteration.

### Implementation

To efficiently grab the two largest stones on every iteration, we can use a max heap.

Start by initializing our max heap. In Python, the standard heap is a min heap so we can negate each value to make it a max heap.

Next, we iterate while the max heap has at least 2 elements:

–
Pop the two largest elements off the max heap, x and y (must be negated to get the actual values)
–
If x > y, swap them
–
If x == y, continue to the next iteration, no new stones added (both destroyed)
–
Otherwise, add y-x to the heap (must be negated to maintain max heap property)

When the iteration completes, we either have 1 or 0 elements in the max heap, return the element or 0 if its empty.

### Edge-cases

Remember to negate when adding and negate when popping from the heap to ensure the max heap property is satisfied and we are comparing the actual stone values.

–
Time: O(n log n), we iterate over all stones once and in each iteration we are popping from the heap which is O(log n).
–
Space: O(n), the max heap will start with all elements.

### Complexity

## solution

python

from typing import List
import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        max_heap = []
        for stone in stones:
            heapq.heappush(max_heap, -stone)

        while len(max_heap) > 1:
            x, y = -heapq.heappop(max_heap), -heapq.heappop(max_heap)
            if x > y:
                x, y = y, x
            if x == y:
                continue
            else:
                heapq.heappush(max_heap, -(y-x))

        return -max_heap[0] if max_heap else 0



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--