[LeetCode with Python] 1046. Last Stone Weight

Difficulty : Easy

 

1st Approach : sort and erase one by one(suceeded but too slow)

 

from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones.sort(reverse=True)
        while len(stones) >= 2:
            #print(stones)
            first = stones.pop(0)
            second = stones.pop(0)
            diff = first - second
            if diff:
                diff_i = 0
                for i in range(len(stones)):
                    if diff >= stones[i]:
                        diff_i = i
                        break
                if stones and diff < stones[-1]:
                    diff_i = len(stones)
                stones.insert(diff_i, diff)
        return stones[0] if stones else 0


if __name__ == "__main__":
    #nums = [2,7,4,1,8,1]
    nums = [3, 7, 8]
    sol = Solution()
    print(sol.lastStoneWeight(nums))

 

2nd Approach : use heap (so fast) - solution from (https://leetcode.com/problems/last-stone-weight/discuss/294956/JavaC%2B%2BPython-Priority-Queue)

 

from typing import List
import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        arr = [-num for num in stones]
        heapq.heapify(arr)
        while len(arr) > 1:
            print(arr)
            heapq.heappush(arr, heapq.heappop(arr) - heapq.heappop(arr))
        
        return -arr[0] if arr else 0


if __name__ == "__main__":
    #nums = [2,7,4,1,8,1]
    nums = [3, 7, 8]
    sol = Solution()
    print(sol.lastStoneWeight(nums))