# Last Stone Weight

Aug 2nd, 2021 (edited)
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import heapq
2.
3. class Solution:
4.     def lastStoneWeight(self, stones: List[int]) -> int:
5.         # 1) Heapify the stones input
6.         # Use negative elements to simulate a max heap, because
7.         # Python's heapq implementation makes a min heap by default.
8.         heap = [-elem for elem in stones]
9.         heapq.heapify(heap)
10.
11.         # 2) While heap length > 1
12.         while len(heap) > 1:
13.             # Heap pop twice
14.             heaviest1 = -heapq.heappop(heap)
15.             heaviest2 = -heapq.heappop(heap)
16.
17.             # Smash
18.             remainder = heaviest1 - heaviest2
19.
20.             # If remainder > 0
21.             if remainder > 0:
22.                 # Heap push it
23.                 heapq.heappush(heap, -remainder)
24.
25.         # 3) Return what's left in heap, if any.
26.         if len(heap) == 1:
27.             return -heap[0]
28.
29.         # If nothing in heap, return 0.
30.         return 0