Last Stone Weight

Heap

15 min

Problem Statement

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 two heaviest 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

Example 1:

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

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

Output: 1

Solution

This problem can be solved efficiently using a max heap. We add all the stone weights to a max heap. Then, as long as there are more than one stone in the heap, we extract the two heaviest stones, smash them, and add the result back to the heap if it's not zero.

Algorithm Steps

Create a max heap from the `stones` array.
While the heap has more than one element:
Pop the two largest stones.
If they are not equal, push their difference back to the heap.
If the heap is empty, return 0. Otherwise, return the last remaining stone.

Last Stone Weight

Max Heap Approach

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

Output: 0

Progress1 / 1

Ready to start the visualization

Max Heap

Last Stone Weight Solution


import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        stones = [-s for s in stones]
        heapq.heapify(stones)
        
        while len(stones) > 1:
            first = heapq.heappop(stones)
            second = heapq.heappop(stones)
            if second > first:
                heapq.heappush(stones, first - second)
        
        stones.append(0)
        return abs(stones[0])