Last Stone Weight II
Find the smallest possible weight of the last stone by turning the smashing game into splitting the stones into two piles as evenly as possible, solved as subset sum.
Problem Understanding
Last Stone Weight II (LeetCode 1049): each turn you pick two stones of weights x ≤ y and smash them. Equal stones both disappear; otherwise x disappears and y becomes y − x. Return the smallest possible weight of the stone left at the end, or 0 if none is left.
Examples: stones = [2,7,4,1,8,1] → 1; stones = [31,26,33,21,40] → 5.
The Intuition: Two Piles in Disguise
The order of smashes does not matter in the end, only which side each stone lands on:
- Every stone is added or subtracted. The last weight is (one pile) − (the other pile).
- Make the piles even. With total S and a pile of s ≤ S / 2, the result is S − 2s.
- Subset sum. Find every pile weight up to S / 2 that some subset makes, and take the largest.
Step 3 is the same table as Partition Equal Subset Sum, which asks whether s can be exactly S / 2, and Target Sum is the same plus/minus idea with a fixed target.
Interactive Walkthrough
TOTAL 23 · ONE PILE ≤ 11
BASE CASE
stones
dp
0
1
2
3
4
5
6
7
8
9
10
11
stone
:
j
:
Answer
:
The total is 23. One pile should be as close to 11 as possible without going over. dp[0] = true
Next
Add stone 2. Sweep j from 11 down to 2, so it is used at most once
stones
The dp row fills with T as stones are added; at the end the scan walks down from half the total to the first T. Try Heavy stone to see the scan pass several unreachable weights.
Dry Run Table
Input: stones = [2,7,4,1,8,1], total 23, half 11.
| After stone | Reachable pile weights (≤ 11) |
|---|---|
| 2 | 0, 2 |
| 7 | 0, 2, 7, 9 |
| 4 | 0, 2, 4, 6, 7, 9, 11 |
| 1 | every weight from 0 to 11 |
| 8, 1 | unchanged (already all reachable) |
Best pile: 11, the other is 12. Answer: 12 − 11 = 1.
The Solution Template
0/1 knapsack on pile weights up to half the total, then the closest reachable weight.
Last Stone Weight II Code
1var lastStoneWeightII = function(stones) {2 const total = stones.reduce((a, b) => a + b, 0);3 const half = Math.floor(total / 2);4 const dp = new Array(half + 1).fill(false);5 dp[0] = true;6 for (const stone of stones) {7 for (let j = half; j >= stone; j--) {8 dp[j] = dp[j] || dp[j - stone];9 }10 }11 let best = half;12 while (!dp[best]) best--;13 return total - 2 * best;14};
Edge Cases & Common Mistakes
- One stone: nothing to smash it with; the answer is its weight (best pile 0).
- Simulating greedily: smashing the two heaviest each time is Last Stone Weight I, and it is not optimal here.
- Sweeping j upwards: reuses a stone, overestimating what is reachable.
- Stone heavier than half: it never fits in the small pile; the loop simply does nothing for it.
- Returning half − best: the answer is total − 2 · best, the gap between the two piles.
Summary
The last weight is the difference between two piles. Use a 0/1 knapsack to find the heaviest pile not above half the total, best, and return total − 2 · best. O(n · S) time, O(S) space.
More practice: DSA interview questions with answers · patterns cheat sheet