Last Stone Weight II - Solution & Explanation
Problem Statement
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 weightxis destroyed, and the stone of weightyhas new weighty - 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] <= 100
Approach Overview
Problem 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 1: Dynamic Programming Approach
The problem can be thought of as partitioning the stones into two groups with a minimum difference in their total weights. This is similar to a variant of the knapsack problem where we try to fill a knapsack with maximum capacity, close to half of the total sum of stones.
Using dynamic programming, we define a state dp[j] which is true if a sum j can be achieved with the given stones. We traverse through the stones, updating our achievable sums. Finally, we find the largest sum that can be achieved which is less than or equal to half of the total sum of all stones. The answer will be the total sum minus twice this value.
We initialize a boolean array dp[] to track achievable sums. For each stone, we update possible sums in reverse to avoid overwriting results we still need. Finally, we check for the largest achievable sum close to half of the total sum, and the result is derived from total sum minus twice that achievable sum.
Complexity
Time Complexity: O(n * sum/2), where n is the number of stones and sum is the total weight of stones.
Space Complexity: O(sum/2), where sum is the total stone weights.
Approach 2: Backtracking with Memoization Approach
Another approach to solve the Last Stone Weight II problem is by using backtracking with memoization. In this approach, we try to partition the stones into two sets where the difference between the total weights of the two sets is minimized. We can recursively explore all combinations of partitioned stones while keeping track of their sums.
To optimize, we use memoization to store and reuse the results of already calculated differences for sub-problems, reducing redundant calculations and improving performance.
The solution employs a recursive helper function to explore all possible ways to partition the stones with a goal to minimize the difference between two groups. The memoization array memo[][] stores previously computed values to avoid repeated calculations, thereby optimizing the recursive calls.
Complexity
Time Complexity: O(n * total_sum), where n is the length of stones and total_sum is the sum of all stone weights.
Space Complexity: O(n * total_sum), for storing the memoization table.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * sum/2), where n is the number of stones and sum is the total weight of stones. |
| Backtracking with Memoization Approach | Time Complexity: O(n * total_sum), where n is the length of stones and total_sum is the sum of all stone weights. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Last Stone Weight II - Leetcode 1049 - Python • NeetCodeIO • 33,594 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Last Stone Weight II easy or hard?
How to solve Last Stone Weight II in O(n)?
What is the best approach for Last Stone Weight II?
What data structure is used in Last Stone Weight II?
What is the time complexity of Last Stone Weight II?
Last Stone Weight II Python or Java solution approach?
Is Last Stone Weight II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Last Stone Weight II with our built-in code editor and test cases.
Practice on FleetCode