You have a pile of stones with weights stones[i]. Each turn, take the two heaviest stones x <= y and smash them: if they are equal both are destroyed, otherwise the lighter one is destroyed and the heavier one becomes y - x. Repeat until at most one stone is left. Return its weight, or 0 if no stones remain.
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting the array again after every smash works but costs O(n log n) per turn. What we really need is "give me the largest" repeatedly while new values are being inserted, which is exactly what a max-heap does in O(log n). Python only has a min-heap, so we store negated weights.
Algorithm
- Put all stones into a max-heap.
- While the heap has at least two stones, pop the largest
yand the next largestx. - If
y > x, pushy - xback. - Return the remaining stone, or 0 if the heap is empty.
O(n log n)Space: O(n)class Solution: def lastStoneWeight(self, stones: List[int]) -> int: heap = [-s for s in stones] # negate to get a max-heap heapq.heapify(heap) while len(heap) > 1: y = -heapq.heappop(heap) # heaviest x = -heapq.heappop(heap) # second heaviest if y > x: heapq.heappush(heap, -(y - x)) return -heap[0] if heap else 0