You're given an array of stone weights. Repeatedly pick up the two heaviest stones and smash them together: if their weights are equal, both are destroyed; otherwise the lighter is destroyed and the heavier survives with weight equal to the difference. Return the weight of the stone left at the end, or 0 if none remain.
Example
Input stones = [2,7,4,1,8,1]
Output 1
Key Pointers
The two "heaviest" stones need repeated access — a max-heap makes both lookups O(log n) instead of scanning for the top two every round.
Python's heapq is a min-heap only, so simulate a max-heap by pushing negated weights.
Only push a remainder back if the two smashed stones weren't equal — a zero-weight remainder shouldn't exist.
Step-by-Step Analysis
Negate every stone's weight and heapify — the smallest negative is now the heaviest stone.
While more than one stone remains: pop the two heaviest, compute their difference.
If the difference is non-zero, push it back (negated) as a new stone.
Once at most one stone remains, return its weight (or 0 if the heap is empty).
Complexity
Time: O(n log n) — Space: O(n)
Code
import heapq
def lastStoneWeight(stones: list[int]) -> int:
heap = [-s for s in stones]
heapq.heapify(heap)
while len(heap) > 1:
first = -heapq.heappop(heap)
second = -heapq.heappop(heap)
if first != second:
heapq.heappush(heap, -(first - second))
return -heap[0] if heap else 0
Code Explanation
How the solution above works, piece by piece.
Python's heapq is a min-heap, so store negated weights to get a max-heap.
Each round pops the two heaviest stones (negating back to positive).
If they differ, the remainder first - second goes back into the heap; if equal, both are gone.
Stop when at most one stone is left; return it, or 0 if none remain.
Each round is O(log n) and there are at most n rounds: O(n log n).
Visual Walkthrough
Running it on stones = [2, 7, 4, 1, 8, 1]:
Each row: the two heaviest stones smash, and the heap contents afterwards (largest first). The last stone left weighs 1.