# LeetCode 1046: Last Stone Weight — Step-by-Step Visual Trace

**Easy** — Heap | Priority Queue | Array | Simulation

## The Problem

Given an array of stone weights, repeatedly smash the two heaviest stones together until at most one stone remains, returning the weight of the last stone or 0 if no stones remain.

## Approach

Use a max-heap to efficiently find the two heaviest stones at each step. Since Python's heapq implements a min-heap, we store negative values to simulate a max-heap. Extract the two largest stones, and if their weights differ, push the difference back into the heap.

**Time:** O(n log n) · **Space:** O(n)

## Code

```python
import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        max_heap = [-stone for stone in stones]  # Use negative values for max-heap

        heapq.heapify(max_heap)

        while len(max_heap) > 1:
            x = -heapq.heappop(max_heap)  # Extract the largest stone
            y = -heapq.heappop(max_heap)  # Extract the second largest stone

            if x != y:
                heapq.heappush(max_heap, -(x - y))  # Push the remaining weight

        return -max_heap[0] if max_heap else 0
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=1046_last-stone-weight)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=1046_last-stone-weight) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*