Last Stone Weight
We have a collection of 'N' stones, each stone has a positive integer weight.

On each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights 'x' and 'y' with 'x'

Question

Last Stone Weight

We have a collection of 'N' stones, each stone has a positive integer weight.

On each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights 'x' and 'y' with 'x' <= 'y'. The result of this smash will be:

1. If 'x' == 'y', both stones are totally destroyed;

2. If 'x' != 'y', the stone of weight 'x' is totally destroyed, and the stone of weight 'y' has a new weight equal to 'y - x'.

In the end, there is at most 1 stone left. Return the weight of this stone or 0 if there are no stones left.

Input format:

The first line of input contains the integer 'N', representing the total number of stones.

The second line of input contains 'N' single space-separated integers, representing the weights of the stones.

Output Format:

The only output line prints the weight of the last stone, if it exists, 0 otherwise.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

Constraints :

1 <= N <= 10^5
1 <= W <= 10^6

Time Limit: 1 sec

Accepted Answer

This question is about finding the weight of the last stone after repeatedly smashing the two heaviest stones together.

Sort the array of stone weights in descending order.
Repeatedly smash the two heaviest stones together until there is at most 1 stone left.
If there is 1 stone left, return its weight. Otherwise, return 0.

Accepted Answer

Removing From List

We will store the stones in a vector/list and run a while loop until the size of the vector/list is greater than 1

Find the index and weight of the two heaviest stones
Remove those stones from the vector/list using their index
Add their absolute difference to the vector/list if the absolute difference is greater than 0

Space Complexity: O(1)Explanation:

O(1).

Since we are using constant extra space.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where N is the total number of stones we have in the beginning.

The number of stones is N and so the first loop will run at most N times, to find the two heaviest stones it will take O(N), and to remove the two heaviest stones it will again take O(N). Adding another stone if weight > 0 will cost again O(N) time. So the overall time complexity is O(N * (N + N + N)) or O(N ^ 2)

Accepted Answer

Priority Queue

We can use a max priority queue to solve this question. Store the weights of all stones in the queue and then while its size is greater than 1 do the following:

Pop two elements from the queue. These will be the two largest elements in the queue.
Then, find the positive difference between the two popped elements and if it's greater than zero, insert it into the queue.

After you've completed the above process, you should have one element left in the queue. Simply return it.

Space Complexity: O(n)Explanation:

O(N), where N is the total number of stones we have in the beginning.

Since we're making a max priority queue to store the N stones. Therefore space complexity is O(N).

Time Complexity: O(nlogn)Explanation:

O(N * logN), where N is the total number of stones we have in the beginning.

Making the max priority queue takes O(N) time and the popping/inserting of weights takes O(N * logN) time. So overall complexity is O(N * logN).