Last Stone Weight II
Last Stone Weight II: given an array of stone weights stones, each turn you pick two stones and smash them together (the lighter one is destroyed, the heavier one loses weight equal to the lighter). Return the smallest possible weight of the last remaining stone (or 0 if none remain).
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 100
Intuition
Last stone weight ii looks like the previous problem but is not a simulation at all. Any sequence of smashes amounts to assigning each stone a plus or minus sign, and the final stone is the absolute value of the resulting sum.
That reframing is the entire problem:
- Every smash order corresponds to splitting the stones into two groups, and the answer is the smallest possible difference between the group sums.
So minimising the last stone means making the two groups as equal as possible.
With S as the total weight and one group summing to s, the difference is S − 2s. Minimising it means making s as close to S/2 as possible without exceeding it, since the smaller group is at most half the total.
That is subset-sum: find the largest achievable subset sum not exceeding S/2. A boolean DP over sums up to S/2 records which totals are reachable, and the answer is S − 2 × bestSum.
The standard 0/1 knapsack rules apply. Iterate the sum downward for each stone, or a stone gets used more than once and the problem silently becomes unbounded knapsack.
Seed dp[0] = true, since a sum of zero is always achievable by choosing nothing.
After processing every stone, scan downward from S/2 for the largest reachable sum — the first true found gives the closest split.
The common mistake is attempting the greedy simulation from the previous problem. Repeatedly smashing the two largest stones does not minimise the final result, which is why this variant is Medium and the original is Easy.
The key reframing is: smashing stones is assigning +/- signs, and minimising the result is a partition problem. Whenever a problem involves splitting items into two groups to minimise the difference of their sums, it reduces to a subset-sum knapsack with target totalSum / 2. Target sum, equal-partition-sum, and this problem are all the same shape.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n * S) time and O(S) space.
Reframe smashing as signs
Any smash order assigns each stone a plus or minus, and the result is the absolute value of the sum. This is a partition problem, not a simulation.
Minimise the group difference
The stones split into two groups, and the answer is the smallest difference between their sums. Making the groups as equal as possible minimises the last stone.
Target half the total
With total S and one group summing to s, the difference is S - 2s. The goal is the largest s not exceeding S/2 — a subset-sum question.
Build the reachability table
dp[s] records whether sum s is achievable. Seed dp[0] = true, since choosing nothing always reaches zero.
Iterate the sum downward
For each stone, sweep sums from high to low. Sweeping upward lets one stone be used repeatedly, silently turning this into unbounded knapsack.
Scan down for the best sum
After all stones, find the largest reachable sum at or below S/2. The answer is S - 2 * bestSum.
Reject the greedy
Repeatedly smashing the two largest stones does not minimise the result — that is Last Stone Weight, and applying it here is the usual error.
Cost of the tabulation
Each stone sweeps sums up to S/2, giving O(n · S) time and O(S) space — pseudo-polynomial, scaling with the total weight.
Solution & live demo
Common pitfalls
Using totalSum as the target instead of totalSum // 2
target = total_sum
target = total_sum // 2
The best subset sum cannot exceed half the total (the other subset has the rest). Using the full sum makes the DP table twice as large and does not improve the answer — subset sums beyond half are mirrors of sums below half.
Iterating the DP forward instead of backward (allowing re-use of stones)
for s in range(stone, target + 1):
dp[s] = dp[s] or dp[s - stone]for s in range(target, stone - 1, -1):
dp[s] = dp[s] or dp[s - stone]Forward iteration lets a stone's weight be added multiple times in the same pass, turning this into an unbounded knapsack. Each stone can only be used once, so iterate backward.
Returning 2 **best - total_sum instead of total_sum - 2** best
return 2 * best - total_sum
return total_sum - 2 * best
best <= total_sum / 2, so 2 * best <= total_sum and the difference is non-negative. Swapping the order returns a negative value, which is invalid as a weight.
Edge cases
If even count, they cancel perfectly and the answer is 0. If odd count, one stone remains.
No smashing possible. Return the stone's weight. The DP finds subset sum 0, giving weight - 0 = weight.
The answer is |stones[0] - stones[1]|. The DP finds min(stones[0], stones[1]) as the best subset sum.