Last Stone Weight - Leetcode Solution

The Last Stone Weight problem on LeetCode asks you to find the last stone weight remaining after a series of operations on a given array of stones. Each operation involves selecting two stones with the largest weights and smashing them together, resulting in a new stone with a weight equal to the difference between the two selected stones.

You can solve this problem using a Max Heap (Priority Queue) to efficiently select the two largest stones at each step. The steps for solving the Last Stone Weight problem are as follows:

1. Create a Max Heap (Priority Queue) and add all the stones from the input array to it.
2. While the size of the heap is greater than 1, perform the following steps:
   1. Remove the two largest stones from the heap.
   2. Calculate the difference between the two stones.
   3. If the difference is greater than 0, add the new stone to the heap.
3. If the heap is empty, return 0. Otherwise, return the final stone remaining in the heap.

Here is the Python code to implement the above algorithm:

import heapq

def lastStoneWeight(stones: List[int]) -> int:
    # Create a max heap (priority queue) and add all stones to it
    heap = [-stone for stone in stones]
    heapq.heapify(heap)

    # Perform pairwise smashing until only one stone left
    while len(heap) > 1:
        # Remove the two largest stones and calculate the difference
        stone1 = heapq.heappop(heap)
        stone2 = heapq.heappop(heap)
        diff = stone1 - stone2

        # Add the new stone to the heap if difference is greater than 0
        if diff > 0:
            heapq.heappush(heap, -diff)

    # Return the remaining stone weight if any, else return 0
    return -heap[0] if heap else 0

This code has a time complexity of O(n log n) due to the heap operations. It has a space complexity of O(n) since it stores all the stones in the heap.

1