# 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 smallest possible weight of the left 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`

**Algorithm **:

**We have 2 stones x & y**

And There could be 2 Possibilities :

- If both the stones x & y have same weight, then
**x == y, both stones are destroyed** - If they are not equal, then stone y always be greater then stone x, therefore
**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 smallest possible weight of the left stone. If there are no stones left, return 0.

I hope problem statement is absolute clear, now let’s talk about how we gonna solve this problem.

**Let’s take an example,**

**Input**: stones = [2,7,4,1,8,1]**Output**: 1

The very Brute force Idea came in our mind is, why don’t we just sort that array, such that we will have bigger values in the end, and to maintain that highest value in the end, we always gonna sort them once both of the stones will collide.

What I mean is, let’s take our input array:

[2,7,4,1,8,1]Let's sort it:[1,1,2,4,7,8]

Now what we gonna do is, collide the 2 stones and get their difference i.e. `y - x`

[1,1,2,4,7,8] --> y = 8 & x = 7Thus,

y - x --> 8 - 7 = 1

Now we gonna put that one in our array & maintain the order by sorting it back again

[1,1,2,4] add => 1 in our array[1,1,2,4,1] now again sort it,[1,1,1,2,4]

So, we gonna perform the same step for all. Well it’s not a great approach to go with, as our Time Complexity will be much higher.

Let’s code it up (Brute Force)-

Let’s try to optimize it.

`For Optimizing it, we gonna use the help of Heap`

Okay, so we gonna take the same example & now you’ll ask which heap do we have to use??**minHeap OR maxHeap??**

As, you can see we want highest value at the first & lowest value in the last. So, we gonna use **maxHeap**

Let’s create our maxHeap and use the same example i.e.

to fill our heap.**[2,7,4,1,8,1]**

So, our first job is, let’s fill our heap.

`Array [2,7,4,1,8,1]`

| |

| |

| |

| |

| |

| |

--------

maxHeap

Now let’s fill our heap,

Array [2,7,4,1,8,1]

^

| |

| |

| |

| |

| |

| 2 |

--------

maxHeapArray [2,7,4,1,8,1]

^

| |

| |

| |

| |

| 7 |

| 2 |

--------

maxHeapArray [2,7,4,1,8,1]

^

| |

| |

| |

| 7 |

| 4 |

| 2 |

--------

maxHeapArray [2,7,4,1,8,1]

^

| |

| |

| 7 |

| 4 |

| 2 |

| 1 |

--------

maxHeapArray [2,7,4,1,8,1]

^

| |

| 8 |

| 7 |

| 4 |

| 2 |

| 1 |

--------

maxHeapArray [2,7,4,1,8,1]

^

| 8 |

| 7 |

| 4 |

| 2 |

| 1 |

| 1 |

--------

maxHeap

Now it’s time to get the stone x & y using our heap & after calculating

put the new difference in our stack**y - x**

`Array [2,7,4,1,8,1]`

| | y = 8

| | x = 7

| 4 |

| 2 | and their result will be y - x => 8 - 7 = 1

| 1 |

| 1 |

--------

maxHeap

Now put that **1** into our heap & again calculate the result of stone x & y

`Array [2,7,4,1,8,1]`

| | y = 4

| | x = 2

| |

| 1 | and their result will be y - x => 4 - 2 = 2

| 1 |

| 1 |

--------

maxHeap

So, we gonna perform the same step until & unless only 1 element left in our stack.