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:
- Create a Max Heap (Priority Queue) and add all the stones from the input array to it.
- While the size of the heap is greater than 1, perform the following steps:
- Remove the two largest stones from the heap.
- Calculate the difference between the two stones.
- If the difference is greater than 0, add the new stone to the heap.
- 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) { PriorityQueuepq = 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