LeetCode 1046.Last Stone Weight

Intuition

use max_heap to find the 2 largest stone and pop to do operations in each iteration. If max_heap has only one stoone or none, return the stone weight or 0.

Python does not have max_heap by default we make the values negative and put it in min_heap

[2,7,4,1,8,1] (heapify)-> [-8 ...] 
Take note that heap is different from sort as it doesn't maintain sorted order but just the min value at the top

Optimal Solution

class Solution:
	def lastStoneWeight(self, stones: List[int]) -> int:
	
		max_heap = [-stone for stone in stones]
		heapq.heapify(max_heap)
		
		while max_heap:
			if len(max_heap) >= 2:
				largest = -heaq.heappop(max_heap)
				second = -heapq.heappop(max_heap)
			
				if largest != second:
					heapq.heappush(max_heap, -(largest-second))
					
			else:
				return -max_heap[0]
		return 0

Time Complexity

O(N(Log(N))) time complexity -> O(N) for heapify O(N) * O(Log(n)) for pop and push operations inside of while loop

O(N) space complexity