Solution Blog: (sign into leetcode to view)
- https://leetcode.com/problems/last-stone-weight/solutions/3451970/intuitive-python-solution-solution-blog/
Negate the values to be able to convert python's minHeap to maxHeap.
Keep playing the game while you have more than one stone in your heap. With every iteration pop the top two weights from the heap. If the top two weights don't match, put the difference of their weights back on the heap.
At the end if there's nothing left on the heap return 0, otherwise return the remaining weight.
- Time complexity: O(nlogn) heapify complexity
- Space complexity: O(n) for the max_heap
Hope this helped - have an awesome day!
#leetcode #python #tutorial
