{x}
blog image

Last Stone Weight II

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 any two stones and smash them together. Suppose the 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 smallest possible weight of the left stone. If there are no stones left, return 0.

 

Example 1:

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

Example 2:

Input: stones = [31,26,33,21,40]
Output: 5

 

Constraints:

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

1049. Last Stone Weight II

Problem Description

Given an array of integers stones where stones[i] is the weight of the ith stone. In each turn, we choose any two stones and smash them together. If the stones have weights x and y with x <= y, the result 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 a new weight y - x.

The goal is to find the smallest possible weight of the left stone at the end of the game. If there are no stones left, return 0.

Solution Approach

This problem can be efficiently solved using dynamic programming. The core idea is to frame the problem as a subset sum problem. The total weight of all stones is sum(stones). We want to find the largest subset of stones whose total weight is as close to sum(stones) / 2 as possible. The difference between the total weight and twice this subset sum will be the minimum weight of the remaining stone.

Why this works: Imagine we divide the stones into two groups, A and B. If we smash stones within each group until only one stone remains in each group, then the final weight will be the absolute difference between the weights of the remaining stones in group A and group B. To minimize the final weight, we should aim to make the weights of group A and group B as close as possible. This is exactly what the subset sum approach achieves.

Detailed Explanation with Code (Python)

The Python code below implements this dynamic programming solution. We iterate through the stones and build a DP table (dp) where dp[i] represents the maximum weight achievable using a subset of the first i stones.

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s = sum(stones)
        n = s >> 1  # Integer division to get half the total sum
        dp = [0] * (n + 1)  # DP table to store maximum achievable weights
 
        for v in stones:  # Iterate through each stone
            for j in range(n, v - 1, -1):  # Iterate backward to avoid double counting
                dp[j] = max(dp[j], dp[j - v] + v)  # Update DP table
 
        return s - 2 * dp[n]  # Result is the difference between total sum and twice the max subset sum

Time Complexity: O(n*sum), where n is the number of stones and sum is the total weight of the stones. This is because the nested loops iterate through all possible combinations of stones.

Space Complexity: O(sum). This is because the DP table dp has a size proportional to the total weight of stones. The Solution 2 uses optimized space complexity to O(sum/2)

Other Language Implementations

The same approach can be implemented in other languages like Java, C++, and others. The core logic remains the same; the only difference is the syntax and data structures used. See the other language examples provided in the original response for the complete code implementations.

Optimization (Solution 2)

The first solution uses a 2D DP table. However, we can optimize this to use a 1D DP table because we only need to keep track of the maximum weight achievable for each possible sum up to half the total weight. This reduces the space complexity. The code provided in Solution 2 shows this optimized approach. The time complexity remains the same but the space complexity improves to O(sum/2).