MediumArrayDynamic Programming

Last Stone Weight II

1 approach, code in every language

You are given an array of positive integers where each value is the weight of a stone. In each move you pick any two stones and smash them together. If the two stones have weights a and b (assume a is at least b), the smash destroys both stones and produces a new stone of weight a - b; if the weights are equal, both stones are fully destroyed and no new stone remains.

You keep smashing until at most one stone is left. Return the smallest weight the last remaining stone can have. If every stone is destroyed, return 0.

The key observation is that assigning a plus or minus sign to each stone models every possible sequence of smashes. Therefore the task reduces to splitting the stones into two groups so that the difference between their total weights is as small as possible.

Example 1

Input: stones = [2,7,4,1,8,1]

Output: 1

Split into groups with sums 11 and 12 (for example {2,4,7-ish groupings}); the best achievable difference is 12 - 11 = 1, so the smallest last stone weighs 1.

Example 2

Input: stones = [31,26,33,21,40]

Output: 5

The total is 151. The subset sum closest to 151/2 = 75.5 that is reachable is 73, giving 151 - 2*73 = 5.

Constraints

1 <= stones.length <= 30
1 <= stones[i] <= 100
The total sum of stones is at most 30 * 100 = 3 * 10^3

0/1 Subset Sum Toward Half the Total

Partition the stones into two subsets whose sums are as close as possible, then the answer is total minus twice the best reachable subset sum.

Loading animation…

Intuition

Every smash sequence can be described by giving each stone a plus or minus sign, so the final stone weight equals the absolute difference between the two signed groups. Minimizing that difference means splitting the stones into two subsets whose sums are as balanced as possible. If the total is S, we want a subset whose sum is as large as possible without exceeding S/2. This is exactly a 0/1 knapsack (subset-sum) problem where each stone is used at most once and the capacity is S/2. Once we know the best reachable sum b that is at most S/2, the other group has sum S - b, and the answer is (S - b) - b = S - 2b.

Algorithm walkthrough

1Compute the total sum S of all stones and the target capacity half = S / 2 (integer division).
2Create a boolean array reachable of size half + 1 where reachable[s] means some subset sums exactly to s; start with reachable[0] = true.
3For each stone, iterate s from half down to the stone's weight and set reachable[s] to true if reachable[s - stone] was true, so each stone contributes at most once.
4Scan reachable from half downward to find the largest sum best that is achievable.
5Return S - 2 * best, which is the minimized difference between the two groups.

Implementation

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        half = total // 2
        reachable = [False] * (half + 1)
        reachable[0] = True
        for stone in stones:
            for s in range(half, stone - 1, -1):
                if reachable[s - stone]:
                    reachable[s] = True
        best = 0
        for s in range(half, -1, -1):
            if reachable[s]:
                best = s
                break
        return total - 2 * best

Time

O(n * S) where n is the number of stones and S is their total sum, because each stone sweeps the capacity range once.

Space

O(S) for the boolean reachable array sized to half the total.

S is bounded by 30 * 100 = 3000, so the DP table is tiny and the solution runs comfortably within limits.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Trimming The Bar Rack Down is our own problem on the technique behind Last Stone Weight II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free