kai-rocket

Last Stone Weight

Aug 2nd, 2021 (edited)
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.94 KB | None | 0 0
  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
Add Comment
Please, Sign In to add comment