Watch 10 video solutions for Last Stone Weight II, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCodeIO has 30,650 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem Overview: You are given an array of stone weights. Each turn you smash two stones together; equal weights destroy both, otherwise the heavier one becomes the difference. The goal is to minimize the final remaining weight after all possible smashes.
The key observation: smashing stones is equivalent to partitioning the stones into two groups whose total weights are as close as possible. If one group has sum S1 and the other S2, the final weight becomes |S1 - S2|. The task reduces to finding a subset whose sum is as close as possible to half of the total weight.
Approach 1: Backtracking with Memoization (Time: O(n * sum), Space: O(n * sum))
This approach explores all ways to assign each stone to one of two groups. At index i, you decide whether to add the stone weight to the current subset or skip it. Without optimization, this forms a binary decision tree with 2^n states. Memoization stores results for states defined by (index, currentSum), avoiding repeated work.
The recursion tries to build a subset sum as close as possible to total/2. When all stones are processed, compute the difference between the two partitions. Memoization drastically reduces the search space because many recursive paths reach the same state. This approach is useful when demonstrating the transition from brute-force recursion to optimized dynamic programming and reinforces how overlapping subproblems appear in dynamic programming.
Approach 2: Dynamic Programming (Subset Sum / Knapsack) (Time: O(n * sum), Space: O(sum))
The optimal approach models the problem as a classic 0/1 knapsack variant. Compute the total weight of all stones and target half = total / 2. The goal is to find the largest achievable subset sum that does not exceed half.
Create a DP array where dp[s] indicates whether a subset sum s is achievable. Iterate through the stones and update the DP array in reverse order so each stone is used at most once. For every weight w, update dp[s] = dp[s] OR dp[s - w]. After processing all stones, scan from half downward to find the largest achievable sum.
If the best subset sum is best, the final answer becomes total - 2 * best. This works because the other partition automatically contains the remaining weight. The approach runs in linear time relative to the number of stones and the total sum, making it efficient for typical constraints. It also demonstrates a practical use of subset partitioning with arrays and state transitions commonly used in array processing problems.
Recommended for interviews: The dynamic programming subset-sum solution is the expected answer. Interviewers want to see the reduction from stone smashing to partition difference and then the application of a knapsack-style DP. Mentioning the recursive backtracking idea shows problem exploration, but implementing the optimized DP demonstrates strong mastery of dynamic programming patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Memoization | O(n * sum) | O(n * sum) | Useful for explaining recursion and overlapping subproblems before converting to DP |
| Dynamic Programming (Subset Sum / Knapsack) | O(n * sum) | O(sum) | Best practical solution; efficient when total stone weight is reasonably bounded |