Similar Problems
Similar Problems not available
Last Stone Weight - Leetcode Solution
Companies:
LeetCode: Last Stone Weight Leetcode Solution
Difficulty: Easy
Topics: heap-priority-queue array
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.
Last Stone Weight Solution Code
1