1046. Last Stone Weight (Python)

Related Topic

Heap. Greedy.

Description

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
• At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Sample I/O

Example 1

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

Methodology

Use heap + greedy to solve this question. We first heapify the given list to max heap. The pop two value (first two largest value in max heap) if they are not equal, we push the differenc of two value into heap. Iterate the heap until the heap length is smaller than 2, then if heap is not empty return the value otherwise return 0.

def lastStoneWeight(self, stones: List[int]) -> int:
        heap=[]
        for stone in stones:
            heapq.heappush(heap,-stone)
        while len(heap)>=2:
            x1 = heapq.heappop(heap)
            x2 = heapq.heappop(heap)
            if x1 != x2:
                heapq.heappush(heap,(x1-x2))
        return -heap[-1] if heap else 0

BigO

Time complexity : O(nlogn) as we construct heap will take O(nlogn)