# LeetCode 1046: Last Stone Weight

## Problem Restatement

We have a collection of stones, each with a positive weight.

In each round, we smash the two heaviest stones together:

- If equal: both are destroyed.
- If not equal: the lighter is destroyed and the heavier remains with weight `heavier - lighter`.

We repeat until at most one stone is left.

Return the weight of the last stone, or `0` if none remain.

The official constraints state that `1 <= stones.length <= 30` and `1 <= stones[i] <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `stones` |
| Output | Weight of last stone, or `0` |

Function shape:

```python
def lastStoneWeight(stones: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
stones = [2, 7, 4, 1, 8, 1]
```

Smash 8 and 7 → 1. Stones: `[2, 4, 1, 1, 1]`.

Smash 4 and 2 → 2. Stones: `[2, 1, 1, 1]`.

Smash 2 and 1 → 1. Stones: `[1, 1, 1]`.

Smash 1 and 1 → 0. Stones: `[1]`.

Answer:

```python
1
```

## Key Insight

We always need the two largest stones. A max heap gives `O(log n)` access to the largest element.

Python's `heapq` is a min-heap, so negate all values to simulate a max heap.

## Algorithm

1. Push all negated stone weights onto a min heap.
2. While the heap has more than one element:
   - Pop two largest weights.
   - If not equal, push back the difference (negated).
3. Return the remaining weight, or `0` if heap is empty.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | At most `n` smash operations, each O(log n) |
| Space | `O(n)` | Heap storage |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)

        while len(heap) > 1:
            a = -heapq.heappop(heap)
            b = -heapq.heappop(heap)
            if a != b:
                heapq.heappush(heap, -(a - b))

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

## Testing

```python
def run_tests():
    s = Solution()

    assert s.lastStoneWeight([2, 7, 4, 1, 8, 1]) == 1
    assert s.lastStoneWeight([1]) == 1
    assert s.lastStoneWeight([2, 2]) == 0
    assert s.lastStoneWeight([3, 7, 2]) == 2

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Standard example | `1` | Simulation result |
| Single stone | `1` | Nothing to smash |
| Equal stones | `0` | Both destroyed |
| Three stones | `2` | `7-3=4, 4-2=2` |