Last Stone Weight II
Asked at Apple
Problem
You are given an array of stones where stones[i] is the weight. Each turn, you smash two stones together: if they have equal weights, both are destroyed; otherwise, the lighter one is destroyed and the heavier one loses the weight of the lighter. The goal is to minimize the last remaining stone weight. This is equivalent to partitioning the array into two groups with minimum difference.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
How to Think About It
Key insight: smashing two stones is like subtracting one from the other. The final weight is |sum(group1) - sum(group2)|. To minimize this, make the two groups as equal as possible. This is a 0-1 knapsack: pick stones to sum to as close as possible to total_sum / 2.
Define dp[i] = True if you can achieve sum i using a subset of stones. Initialize dp[0] = True. For each stone, iterate backward from target to stone weight, updating dp[j] |= dp[j - stone].
The target is total_sum // 2. After filling the DP, find the largest j <= target where dp[j] is True. The answer is total_sum - 2 * j. This represents the minimum difference between the two groups.
Why iterate backward? If you iterate forward, you might use the same stone multiple times (unbounded knapsack). Backward iteration ensures 0-1 knapsack behavior: each stone is used at most once.
Visual walkthrough: stones = [2, 7, 4, 1, 8, 1]. Total = 23. Target = 11.
- dp starts as [T, F, F, ..., F] (size 12).
- Stone 2:
dp[2]= True. - Stone 7:
dp[7]= True,dp[9]= True (2+7). - Stone 4:
dp[4]= True,dp[6]= True (2+4),dp[11]= True (7+4). - Stone 1:
dp[1]= True,dp[3]= True,dp[5]= True,dp[7]= True (already),dp[8]= True,dp[10]= True,dp[11]= True (already). - Stone 8:
dp[8]= True,dp[10]= True,dp[11]= True (already). - Stone 1:
dp[1]= True, etc.
Largest j <= 11 wheredp[j]= True: j = 11.
Answer: 23 - 2*11 = 1.
Time: O(n * target) where target = total_sum / 2. Space: O(target). This is efficient when total sum is reasonable (e.g., stones[i] <= 100, n <= 30).
Optimal Approach
0-1 knapsack to find the subset that sums to the largest value <= total_sum / 2.
- Compute
total = sum(stones). Target =total // 2. - Create boolean
dparray of sizetarget + 1.dp[0] = True. - For each stone:
a. For j from target down to stone:dp[j] |= dp[j - stone]
- Find largest j where
dp[j]is True. - Return
total - 2 * j.
Walkthrough: stones = [31, 26, 33, 21, 40]. Total = 151. Target = 75.
- DP fills up marking reachable sums.
- Largest j <= 75: j = 74.
- Answer: 151 - 2*74 = 3.
Time: O(n * target). Space: O(target).
What Trips People Up in Real Interviews
Not recognizing this as a partition problem. The stone-smashing process is confusing, but the final weight is always |sum(group1) - sum(group2)|. Framing it as partition makes the knapsack approach obvious.
Iterating forward in the DP array. Forward iteration turns it into an unbounded knapsack (using the same stone multiple times). Always iterate backward from target down to stone weight.
Off-by-one in the target. Use total_sum // 2 (integer division). If total_sum is odd, target is floor(total/2), and the answer will be at least 1.
Forgetting that dp[0] = True. Base case: you can always achieve sum 0 (empty subset). Without this, no other sums will be marked as reachable.
Returning total_sum - target instead of total_sum - 2 * j. The answer is the difference between the two groups: total_sum - 2 * best_sum, not total_sum - best_sum.
Solution Code
def lastStoneWeightII(stones):
total = sum(stones)
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for stone in stones:
for j in range(target, stone - 1, -1):
dp[j] = dp[j] or dp[j - stone]
for j in range(target, -1, -1):
if dp[j]:
return total - 2 * j
return totalFrequently Asked Questions
What is the Last Stone Weight II problem?
You are given an array of stones where stones[i] is the weight. Each turn, you smash two stones together: if they have equal weights, both are destroyed; otherwise, the lighter one is destroyed and the heavier one loses the weight of the lighter. The goal is to minimize the last remaining stone weight. This is equivalent to partitioning the array into two groups with minimum difference.
How do you solve Last Stone Weight II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Last Stone Weight II?
Last Stone Weight II is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Last Stone Weight II?
- Not recognizing this as a partition problem. The stone-smashing process is confusing, but the final weight is always |sum(group1) - sum(group2)|. Framing it as partition makes the knapsack approach obvious.
- Iterating forward in the DP array. Forward iteration turns it into an unbounded knapsack (using the same stone multiple times). Always iterate backward from target down to stone weight.
- Off-by-one in the target. Use `total_sum // 2` (integer division). If total_sum is odd, target is `floor(total/2)`, and the answer will be at least 1.
- Forgetting that `dp[0]` = True. Base case: you can always achieve sum 0 (empty subset). Without this, no other sums will be marked as reachable.
- Returning `total_sum - target` instead of `total_sum - 2 * j`. The answer is the difference between the two groups: `total_sum - 2 * best_sum`, not `total_sum - best_sum`.