The problem
You have stones with weights stones[i]. Each turn, take the two heaviest, y ≥ x, and smash them: if they weigh the same, both are destroyed; otherwise the lighter is destroyed and the heavier now weighs y − x.
When at most one stone is left, return its weight, or 0 if none is.
Examples
01
- Input
stones = [2, 7, 4, 1, 8, 1]
- Output
1
02
- Input
stones = [1]
- Output
1
Constraints
- 1 ≤ stones.length ≤ 30
- 1 ≤ stones[i] ≤ 1000
The idea
Every turn needs the two heaviest stones, and may put a new stone back. A max-heap — the largest always on top — gives exactly that: remove the top twice, and push the difference back if it is not zero.
Each turn removes at least one stone, so there are at most n turns, each costing log n.
- Time
- O(n log n)
- Space
- O(n) — the heap
Solution · every language run against every case
class Solution: def lastStoneWeight(self, stones: List[int]) -> int: heap = [-s for s in stones] # Python's heap gives the smallest, so store weights negated heapify(heap) while len(heap) > 1: y, x = -heappop(heap), -heappop(heap) # the two heaviest, y >= x if y > x: heappush(heap, -(y - x)) return -heap[0] if heap else 0