Last Stone Weight

Photo by Shashank Rana on Unsplash

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 = 7
Thus,
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. [2,7,4,1,8,1] to fill our heap.

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  |
--------
maxHeap
Array           [2,7,4,1,8,1]
				                   ^
|     |
|     |		
|     |  
|     |
|  7  |
|  2  |
--------
maxHeap
Array           [2,7,4,1,8,1]
				                     ^
|     |
|     |		
|     |  
|  7  |
|  4  |
|  2  |
--------
maxHeap
Array           [2,7,4,1,8,1]
				                       ^
|     |
|     |		
|  7  |  
|  4  |
|  2  |
|  1  |
--------
maxHeap
Array           [2,7,4,1,8,1]
				                         ^
|     |
|  8  |		
|  7  |  
|  4  |
|  2  |
|  1  |
--------
maxHeap
Array           [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 y - x put the new difference in our stack

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.