Remove Stones To Minimize The Total - Leetcode Solution

Problem Statement:

You are given an integer array 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 smallest possible weight of the left stone. If there are no stones left, return 0.

Solution:

The brute force solution to the problem would be to simulate the game. We can repeatedly find the two heaviest stones, smash them together and update the given input array with the new stone weight accordingly. We can then repeat this process until there is only one stone left, or no stones left.

This solution will work, but it has a time complexity of O(nlogn * n) since we need to sort the array on each iteration. This is not very efficient and may take too long for large inputs.

A more optimized solution uses heap data structure to keep track of the heaviest stone. We can create a max heap and push all the input stones into the heap. Then, until there is only one stone left, we can pop the two heaviest stones from the heap, smash them together, and push the new stone back into the heap.

To implement the above solution, we can use the heapq module in Python to create a heap and perform heap operations. We can use the heappop() to pop the two heaviest stones, and heappush() to push the new stone back into the heap. This solution has a time complexity of O(nlogn) since we perform n heap operations.

Here's the Python code for the optimized solution:

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Create a max heap
        heap = [-x for x in stones]
        heapq.heapify(heap)
        
        # Perform smash operations until there is only one stone left
        while len(heap) > 1:
            y, x = -heapq.heappop(heap), -heapq.heappop(heap)
            
            if x != y:
                heapq.heappush(heap, y - x)
        
        # Return the remaining stone weight
        return -heap[0] if heap else 0

Time Complexity: O(nlogn)

1