1046. Last Stone Weight

1046. Last Stone Weight#

Difficulty: Easy

Link to Problem: To see the Last Stone Weight problem on LeetCode, click here!

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, you 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.
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.

Constraints:

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

Probelm Explanation:#

The “Last Stone Weight” problem involves a game played with a collection of stones, each stone having a certain weight. The goal is to find the weight of the last remaining stone after applying a specific set of rules.

Here’s how the game works:

You start with an array of stones, where each stone is represented by its weight. The weights of the stones are given in the input as an array.
In each turn of the game, you select the two heaviest stones from the remaining stones. If there is only one stone left, you’ve found the answer.
If there are two stones with weights x and y, where x is less than or equal to y, the following happens:
- If x is equal to y, both stones are completely destroyed, and they are removed from the array of stones.
- If x is not equal to y, the stone with weight x is destroyed, and the stone with weight y now has a new weight of y - x. The stone with weight x is removed from the array, and the modified stone with weight y - x remains in the array.
The game continues with the modified array of stones until there is at most one stone left.
The goal is to find the weight of the last remaining stone, or if there are no stones left, return 0.

Solution:#

Here’s a Python function to implement this algorithm:

import heapq

def lastStoneWeight(stones):
    # Convert the input list to a max heap (negate the values to simulate a max heap)
    max_heap = [-stone for stone in stones]
    heapq.heapify(max_heap)

    # Continue as long as there are more than 1 stone in the heap
    while len(max_heap) > 1:
        # Get the two heaviest stones
        y = -heapq.heappop(max_heap)  # Get the heaviest stone and negate it back to positive
        x = -heapq.heappop(max_heap)  # Get the second heaviest stone and negate it back to positive

        # Calculate the new stone's weight after smashing
        if x != y:
            new_stone = y - x
            heapq.heappush(max_heap, -new_stone)  # Negate the value and push it back to the heap

    # If there is one stone left, return its weight (negate it back to positive)
    if max_heap:
        return -max_heap[0]
    else:
        return 0

Explanation:#

The code defines a Python function called lastStoneWeight that takes a list of stone weights as input. It aims to find the weight of the last remaining stone after playing the stone smashing game described in the problem statement.

Here’s a step-by-step explanation of the code:

We import the heapq library, which allows us to create and manipulate a heap (priority queue).
Inside the lastStoneWeight function:
- We create a max heap (negating stone weights to simulate a max heap) using the heapq.heapify function. This heap will keep track of the heaviest stones.
- We enter a loop that continues as long as there are more than 1 stone in the heap.
- Inside the loop, we:
  - Retrieve and negate the heaviest stone (y) from the heap.
  - Retrieve and negate the second heaviest stone (x) from the heap.
  - Calculate the new stone’s weight after smashing (y - x), and negate it back to simulate a max heap.
  - Add the new stone back to the heap using heapq.heappush.
After the loop, if there is one stone left in the heap, we retrieve and negate it to get its actual weight, and return it as the result.
If there are no stones left (the heap is empty), we return 0, indicating that no stones remain.
Finally, we provide two test cases to demonstrate the function’s usage and correctness.

In summary, the code efficiently implements the stone smashing game by maintaining a max heap, selecting the heaviest stones in each turn, smashing them, and updating the heap until there is at most one stone left. It then returns the weight of the last remaining stone or 0 if there are no stones left.

Test cases:#

Here’s how you can use this solution:

# Example 1: 

stones1 = [2, 7, 4, 1, 8, 1]
print(lastStoneWeight(stones1))  # Output: 1

# Example 2: 

stones2 = [1]
print(lastStoneWeight(stones2))  # Output: 1

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided Python code for the “Last Stone Weight” problem:

Time Complexity:

The heapq.heapify operation to create the max heap from the input stone weights has a time complexity of O(n), where n is the number of stones.
The loop that continues until there are more than 1 stone in the heap performs the following operations in each iteration:
- Retrieving and negating the heaviest stone (y) from the heap, which takes O(log n) time.
- Retrieving and negating the second heaviest stone (x) from the heap, also taking O(log n) time.
- Calculating the new stone’s weight and pushing it back into the heap using heapq.heappush, which takes O(log n) time.
In the worst case, the loop runs until there is only one stone left, which requires approximately (n-1) iterations.

Overall, the dominant time complexity is O(n) for the initial heap creation, and within the loop, each iteration takes O(log n) time. Therefore, the overall time complexity of the algorithm is O(n log n).

Space Complexity:

The space complexity is primarily determined by the space required for the max heap. In the worst case, this heap can contain all the stones, so the space complexity for the heap is O(n).
The rest of the variables used in the function (e.g., x, y, new_stone) require only constant space, so they do not significantly contribute to the space complexity.

Therefore, the overall space complexity of the algorithm is O(n) due to the space used for the max heap.

In summary:

Time Complexity: \(O(n\ log\ n)\)
Space Complexity: \(O(n)\)

The algorithm is efficient enough to handle the problem’s constraints, as the worst-case time and space complexities are both linearithmic in terms of the number of stones.

Challenging Exercises:#

Kth Last Stone Weight: Modify the problem to find the weight of the Kth last remaining stone, where K is an integer input. Your function should work efficiently for large values of K.
Multiple Stones Smash: Modify the problem so that instead of smashing two stones at a time, you can smash up to K stones at each turn, where K is an integer input. Determine the weight of the last remaining stone in this variation.