> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/heap ]
> [project group:: neetcode 150]
> [difficulty:: easy]
> [status:: to begin]
> [link:: https://leetcode.com/problems/last-stone-weight/]
> [up:: [[Leetcode MOC]]]
## Problem
You are given an array of integers `stones` where `stones[i]` is the weight of the `ith` stone.
We are playing a game with the stones. On each turn, we choose the **heaviest two stones** and smash them together. Suppose the heaviest two stones have weights `x` and `y` with `x <= y`. The result of this smash is:
- If `x == y`, both stones are destroyed, and
- If `x != y`, the stone of weight `x` is destroyed, and the stone of weight `y` has new weight `y - x`.
At the end of the game, there is **at most one** stone left.
Return _the weight of the last remaining stone_. If there are no stones left, return `0`.
**Example 1:**
**Input:** stones = [2,7,4,1,8,1]
**Output:** 1
**Explanation:**
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
**Example 2:**
**Input:** stones = [1]
**Output:** 1
**Constraints:**
- `1 <= stones.length <= 30`
- `1 <= stones[i] <= 1000`
## Solution
### Mine
#### Python
```python
import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [stone * -1 for stone in stones]
heapq.heapify(stones)
while len(stones) > 1:
first_stone = heapq.heappop(stones) * -1
second_stone = heapq.heappop(stones) * -1
if first_stone != second_stone:
new_stone = abs(first_stone - second_stone) * -1
heapq.heappush(stones, new_stone)
if stones:
return stones[0] * -1
else:
return 0
```
### Neetcode's
## Things I Learned
## Scratchpad
We know to use a max heap here. For the game:
1. `heappop` twice to get the two stones
2. Do nothing if they're equal, if not take the difference and add that back to the heap
3. Continue until the size of the heap is 1