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[0] 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) {
            pq.add(stone);
        }
        while (pq.size() > 1) {
            int stone1 = pq.remove();
            int stone2 = pq.remove();
            if (stone1 != stone2) {
                int diff = Math.abs(stone1 - stone2);
                pq.add(diff);
            }
        }
        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[0]
        stone2 = stones[1]
        
        # 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[0]
    
    # 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] : 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[0]; 
              
        // 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