Last Stone Weight

It requires two major steps. In the first step, you need to find the two heaviest stones. In the second step, you smash these stones together according to the rules given. You repeat these steps until there is at most one stone left.

One efficient way to keep track of the two heaviest stones is to use a max heap, a type of priority queue. In Python, you can use the heapq library, which provides an implementation of heap queue algorithm (priority queue algorithm) using lists. However, heapq in Python implements a min-heap, so we’ll store our stones as negative numbers to mimic a max heap.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Convert all stones to negative and push into max heap
        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)

        # Process until there is one or no stone left
        while len(max_heap) > 1:
            # The two heaviest stones
            stone_1 = heapq.heappop(max_heap)
            stone_2 = heapq.heappop(max_heap)
            # If they are not of equal weight, push the difference back into max heap
            if stone_1 != stone_2:
                heapq.heappush(max_heap, stone_1 - stone_2)

        # If there is one stone left, return its weight else return 0
        if max_heap: return -max_heap[0]
        else: return 0

In this code, we first create a max heap from the stones array. Then, in a loop, we pop two stones from the max heap, which will be the two heaviest stones because of the properties of the max heap. We then compare these two stones. If they are of equal weight, they both get destroyed. If they are not of equal weight, we push the difference back into the max heap. We repeat this process until there is one or no stone left. Finally, we return the weight of the last remaining stone if it exists, else we return 0. Note that because we’re working with a min-heap representation of a max-heap, we multiply the result by -1 to convert it back to positive.