Last Stone Weight II

Problem Description

You are given an array of integers stones where stones[i] is the weight of the i-th stone. We are playing a game with the stones. On each turn, we choose any two stones and smash them together. If 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.

Key Insights

• The problem can be viewed as a variation of the subset sum problem.
• The goal is to minimize the absolute difference between two groups of stones.
• Dynamic programming can be used to explore possible sums of stone weights, allowing us to find the minimum leftover weight efficiently.

Space and Time Complexity

Time Complexity: O(n * totalWeight), where n is the number of stones and totalWeight is the sum of all stone weights. Space Complexity: O(totalWeight), used to store possible sums of weights.

Solution

The approach uses dynamic programming to find the possible sums of weights that can be achieved using the stones. We create a boolean array dp where dp[j] indicates whether a sum of j can be achieved with the given stones. By iterating through the stones and updating the dp array, we can determine the maximum achievable weight that is less than or equal to half of the total weight of the stones. The final answer is then computed as the difference between the total weight and twice the largest achievable weight.

Code Solutions