1046. Last Stone Weight | LeetCode Using Python

I solve the “1046. Last Stone Weight” problem from LeetCode using Python. I demonstrate how to efficiently solve this challenge by simulating a max-heap with Python’s heapq module. The video walks through the steps of converting stone weights into a heap, processing the two heaviest stones, and handling the results to determine the final weight of the last remaining stone. Below, you’ll find the complete code along with detailed comments explaining each part of the solution.

Python code:

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        """
        #We'll use a heap to solve this problem
        #Since python doesn't have a max_heap module our heap is min_heap we have to negate our value
        """
        max_heap =[-stone for stone in stones] #negate all value in stone list
        heapq.heapify(max_heap) #This is a Time complexityy of O(n) to turn list in heap

        #now we have a max heap to pop and push our largest number form efficient(at a O(log)n time complexity)


        #At the end of the game, there is at most one stone left.
        while len(max_heap) > 1:
            y = -heapq.heappop(max_heap) #pop larger value out and convert it to a positive value
            x = -heapq.heappop(max_heap) #pop our next largest value or equal to y and convert it to a positive value
            #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.
            if x != y:
                heapq.heappush(max_heap, -(y- x)) #push it pack to max_heap after turn it back to a negative

        #****Return the weight of the last remaining stone. If there are no stones left, return 0.****
        return -max_heap[0] if max_heap else 0

        #Time complexity is O(nlogn
        #Space complexity O(n)