{x}
blog image

Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

 

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

Solution Explanation: Last Stone Weight

This problem involves simulating a process of smashing stones together until at most one remains. The most efficient approach uses a priority queue (heap) data structure.

Approach:

  1. Initialization: Create a max-heap (priority queue that prioritizes the largest elements). Insert all stone weights into the heap. We use a max-heap because we need to efficiently access the two heaviest stones in each iteration. Note that in some languages (like Python), the heap is a min-heap by default, so we negate the weights before inserting them and negate them back when retrieving.

  2. Iteration: While the heap contains more than one stone:

    • Remove the two heaviest stones (y and x, with y >= x).
    • If x and y are equal, both are destroyed (do nothing).
    • If x and y are unequal, the resulting stone weight is y - x. Insert this new weight back into the heap.

  3. Result: After the loop, if the heap is empty, there are no stones left, so return 0. Otherwise, the single remaining stone's weight (which is the largest) is at the top of the heap, so return its weight (after potentially negating it back if a min-heap was used initially).

Time Complexity: O(N log N), where N is the number of stones. Building the heap takes O(N log N) time. Each removal and insertion operation takes O(log N) time, and we perform at most N such operations.

Space Complexity: O(N) to store the heap.

Code Explanation (Python):

import heapq
 
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        h = [-x for x in stones]  # Negate weights for min-heap in Python
        heapq.heapify(h)          # Build the heap
        while len(h) > 1:
            y = -heapq.heappop(h) # Get the largest (negate back)
            x = -heapq.heappop(h) # Get the second largest (negate back)
            if x != y:
                heapq.heappush(h, x - y) # Add the difference
        return 0 if not h else -h[0] # Return the last stone's weight (or 0)

The other language solutions follow the same logic, but adapt to the specific heap implementations in those languages. For instance, Java and C++ have built-in priority queues that are max-heaps by default, simplifying the code somewhat. Go requires a custom heap implementation using container/heap, and Javascript/Typescript require using a library like MaxPriorityQueue since Javascript doesn't natively support heaps.