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:
x == y, both stones are destroyed, andx != 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 <= 301 <= stones[i] <= 100The key insight for #1049 Last Stone Weight II is that repeatedly smashing stones is equivalent to dividing the stones into two groups whose total weights are as close as possible. The final remaining weight equals the absolute difference between the sums of these two groups.
This converts the problem into a classic subset sum / partition problem. Let the total weight of all stones be S. We try to find a subset of stones whose sum is as close as possible to S / 2. If we can achieve a subset sum x, the remaining stones sum to S - x, and the leftover stone weight becomes S - 2x.
A common approach uses dynamic programming where dp[i] tracks whether a subset with weight i is achievable. By iterating through stones and updating possible sums up to S/2, we find the largest achievable subset sum closest to this target. The result is computed from that value. This approach efficiently reduces the search space and leverages classic knapsack-style DP.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Subset Sum / Knapsack) | O(n * S) | O(S) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Think of the final answer as a sum of weights with + or - sign symbols infront of each weight. Actually, all sums with 1 of each sign symbol are possible.
Use dynamic programming: for every possible sum with N stones, those sums +x or -x is possible with N+1 stones, where x is the value of the newest stone. (This overcounts sums that are all positive or all negative, but those don't matter.)
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar subset partition variations frequently appear in technical interviews. Companies often use it to evaluate a candidate's understanding of dynamic programming and knapsack-style optimization.
Yes, it is a classic dynamic programming problem related to the 0/1 knapsack or subset partition problem. The goal is to determine which subset sums are achievable up to half of the total stone weight.
The optimal approach treats the problem as a partition or subset sum problem. By trying to split the stones into two groups with sums as close as possible, dynamic programming can efficiently compute the minimal possible difference.
A dynamic programming array or boolean DP table works best for tracking achievable subset sums. Some optimized solutions also use bitsets to represent reachable weights and update them efficiently.