## Algorithm

Problem Name: 1046. Last Stone Weight

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`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int stone : stones) {
pq.add(stone);
}
while (pq.size() > 1) {
int firstStone = pq.poll();
int secondStone = pq.poll();
if (firstStone != secondStone) {
pq.add(firstStone - secondStone);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
}
``````
Copy The Code &

Input

cmd
stones = [2,7,4,1,8,1]

Output

cmd
1

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const lastStoneWeight = function(stones) {
stones.sort((a, b) => a - b)
while (stones.length > 1) {
const num = Math.abs(stones.pop() - stones.pop())
stones.splice(stones.findIndex(item => item >= num), 0, num)
}
return stones[0]
};
``````
Copy The Code &

Input

cmd
stones = [2,7,4,1,8,1]

Output

cmd
1

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
for _ in range(len(stones) - 1):
bisect.insort(stones, stones.pop() - stones.pop())
return stones[0]
``````
Copy The Code &

Input

cmd
stones = [1]

Output

cmd
1

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _1046_LastStoneWeight
{
public int LastStoneWeight(int[] stones)
{
var counts = new int[1001];
var maxWeight = int.MinValue;

foreach (var stone in stones)
{
counts[stone]++;
maxWeight = Math.Max(maxWeight, stone);
}

var biggestWeight = 0;
var currentWeight = maxWeight;
while (currentWeight > 0)
{
if (counts[currentWeight] == 0)
{
currentWeight--;
continue;
}
if (biggestWeight == 0)
{
counts[currentWeight] %= 2;
if (counts[currentWeight] == 1)
{
biggestWeight = currentWeight;
counts[currentWeight] = 0;
}
currentWeight--;
}
else
{
counts[currentWeight]--;
if (biggestWeight - currentWeight <= currentWeight)
{
counts[biggestWeight - currentWeight]++;
biggestWeight = 0;
}
else
{
biggestWeight -= currentWeight;
}
}
}
return biggestWeight;
}
}
}
``````
Copy The Code &

Input

cmd
stones = [1]

Output

cmd
1