# Solution For Last Stone Weight

The Last Stone Weight problem on LeetCode asks you to find the last stone weight remaining after a series of operations on a given array of stones. Each operation involves selecting two stones with the largest weights and smashing them together, resulting in a new stone with a weight equal to the difference between the two selected stones.

You can solve this problem using a Max Heap (Priority Queue) to efficiently select the two largest stones at each step. The steps for solving the Last Stone Weight problem are as follows:

1. Create a Max Heap (Priority Queue) and add all the stones from the input array to it.
2. While the size of the heap is greater than 1, perform the following steps:
3. Remove the two largest stones from the heap.
4. Calculate the difference between the two stones.
5. If the difference is greater than 0, add the new stone to the heap.
6. If the heap is empty, return 0. Otherwise, return the final stone remaining in the heap.

Here is the Python code to implement the above algorithm:

“`
import heapq

def lastStoneWeight(stones: List[int]) -> int:
# Create a max heap (priority queue) and add all stones to it
heap = [-stone for stone in stones] heapq.heapify(heap)

``````# Perform pairwise smashing until only one stone left
while len(heap) > 1:
# Remove the two largest stones and calculate the difference
stone1 = heapq.heappop(heap)
stone2 = heapq.heappop(heap)
diff = stone1 - stone2

# Add the new stone to the heap if difference is greater than 0
if diff > 0:
heapq.heappush(heap, -diff)

# Return the remaining stone weight if any, else return 0
return -heap if heap else 0
``````

“`

This code has a time complexity of O(n log n) due to the heap operations. It has a space complexity of O(n) since it stores all the stones in the heap.

## Step by Step Implementation For Last Stone Weight

```We can use a PriorityQueue to keep track of the stones in order from heaviest to lightest. We can then iterate through the stones, removing the two heaviest stones and smashing them together. If the resulting stone is heavier than 0, we can add it back into the PriorityQueue. We can continue doing this until there is only one stone left, which will be the last stone weight.

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue pq = new PriorityQueue<>(Comparator.reverseOrder());
for (int stone : stones) {
}
while (pq.size() > 1) {
int stone1 = pq.remove();
int stone2 = pq.remove();
if (stone1 != stone2) {
int diff = Math.abs(stone1 - stone2);
}
}
return pq.isEmpty() ? 0 : pq.remove();
}
}```
```def lastStoneWeight(stones):

# sort the list in reverse order
stones.sort(reverse = True)

# while there are more than 1 element in the list
while len(stones) > 1:

# take the first 2 elements from the list
stone1 = stones
stone2 = stones

# if the 2 stones are equal, remove them from the list
if stone1 == stone2:
stones.remove(stone1)
stones.remove(stone2)

# if the 2 stones are not equal, take the difference and add it back to the list
else:
diff = stone1 - stone2
stones.remove(stone1)
stones.remove(stone2)
stones.append(diff)

# if there is only 1 element in the list, return that element
if len(stones) == 1:
return stones

# if the list is empty, return 0
else:
return 0```
```var lastStoneWeight = function(stones) {

// sort the array in descending order
stones.sort((a, b) => b - a);

// as long as there are at least 2 stones in the array:
while (stones.length >= 2) {

// take the 2 heaviest stones from the array
const [stone1, stone2] = stones.splice(0, 2);

// if the stones are not equal:
if (stone1 !== stone2) {

// calculate the weight of the new stone
const newStone = Math.abs(stone1 - stone2);

// put the new stone back into the array
stones.push(newStone);

// sort the array again
stones.sort((a, b) => b - a);
}
}

// if there is only 1 stone left, return its weight
// otherwise, return 0
return stones.length === 1 ? stones : 0;
};```
```There are a number of ways to approach this problem. One approach would be to use a min heap to keep track of the stones. We would first add all of the stones to the heap, and then we would remove the two largest stones and add their weights together. We would then add this new stone back into the heap and continue until there was only one stone left. This stone would be the last stone weight.

Another approach would be to use a sorting algorithm to sort the stones in descending order. We would then iterate through the sorted list, removing the two largest stones and adding their weights together. We would then add this new stone back into the list and continue until there was only one stone left. This stone would be the last stone weight.```
```using System;

class GFG
{

// Function to calculate the last
// stone weight
static int lastStoneWeight(int[] stones)
{

// To store the size of array
int size = stones.Length;

// To store the maximum value
int maxVal = 0;

// To store the maximum value's
// index
int maxValIndex = 0;

// Run the outer loop till
// all the elements are processed
while (size > 1)
{

// To find the maximum value in
// the array
for (int i = 0; i < size; i++)
{
if (stones[i] > maxVal)
{
maxVal = stones[i];
maxValIndex = i;
}
}

// To replace the found maximum
// value with the last element
stones[maxValIndex] = stones[size - 1];

// Reduce the size of array
size--;

// If array contains only one element
if (size == 1)
break;

// To find the second maximum value
maxVal = 0;
for (int i = 0; i < size; i++)
{
if (stones[i] > maxVal)
{
maxVal = stones[i];
maxValIndex = i;
}
}

// If both maximum values are same
if (stones[size - 1] == stones[maxValIndex])
{
size--;
continue;
}

// Subtract the found maximum values
stones[maxValIndex] = stones[size - 1] - stones[maxValIndex];

// Again set the size to size-1
size--;
}

// If array contains only one element
// return it
if (size == 1)
return stones;

// Otherwise return 0
return 0;
}

// Driver Code
public static void Main()
{

// Get the input array
int[] stones = { 2, 7, 4, 1, 8, 1 };

// Print the maximum value
Console.WriteLine(lastStoneWeight(stones));
}
}

// This code is contributed by Smitha Dinesh Semwal```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]