MediumArrayDynamic ProgrammingKnapsackUpdated Sep 2026

1049. Last Stone Weight II

Asked at Apple

Difficulty

Medium

Time

O(n * target), where target = to

Space

O(target)

Pattern

Array

Companies

1

Problem

You get a list of stone weights. You play a game: each turn you pick any two stones and smash them together. If the two weights are equal, both stones vanish. If they are different, the lighter stone vanishes and the heavier stone becomes the difference of the two weights.

Keep smashing until at most one stone is left. Return the smallest possible weight of that last stone. If nothing is left, return 0.

The key idea: every smash is really a subtraction. In the end, the remaining weight equals the absolute difference between the sums of two groups of stones. So you want to split the stones into two groups whose sums are as close as possible.

Smashing = subtracting

stonessum 11274181012345Put 7 and 4 in one group; the other group sums to 12.group A = 11group B = 12answer = |12 - 11| = 1
Each smash removes one stone and shrinks the other, so the final weight is the gap between two groups of stones.

Constraints

  • ●1 <= stones.length <= 30
  • ●1 <= stones[i] <= 100

Examples

Example 1
Inputstones = [2,7,4,1,8,1]
Output1
WhyTotal weight is 23. We can split the stones into a group summing to 11 (for example 7 + 4) and the rest summing to 12. The difference is 12 - 11 = 1, and no split can do better.
Example 2
Inputstones = [31,26,33,21,40]
Output5
WhyTotal weight is 151. The best split is 74 against 77, giving a difference of 3. Wait — the closest reachable sum to 75 is 73, so the difference is 151 - 2*73 = 5.

Asked At

1 companies
CompanyDifficulty
AppleMediumView all Apple questions →

How to Think About It

1

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.

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].

3

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.

4

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.

5

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.

  1. Compute total = sum(stones). Target = total // 2.
  2. Create boolean dp array of size target + 1. dp[0] = True.
  3. For each stone:
    a. For j from target down to stone:
    • dp[j] |= dp[j - stone]
  4. Find largest j where dp[j] is True.
  5. 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).

0-1 knapsack on half the total

dp index0123456789101101234567891011After stones 2, 7 and 4: sums 0, 2, 7, 9 and 11 are reachable.dp index0123456789101101234567891011Adding stone 1 opens 1, 3, 5, 8 and 10; 11 stays reachable.for j = target down to stone:dp[j] = dp[j] or dp[j - stone]answer = total - 2 * best_j
We mark every sum we can build from a subset of stones, then take the largest one that does not pass half the total.
ComplexityTime O(n * target), where target = toSpace O(target)We loop over each stone and each reachable sum up to half the total, and keep only a one-dimensional boolean table.

What Trips People Up in Real Interviews

1

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.

2

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.

3

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.

4

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.

5

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

O(n * target), where target = to time
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 total

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n * target), where target = to time and O(target) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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`.