Last Stone Weight II

Difficulty: Medium Source: NeetCode

Problem

You have a collection of stones with positive integer weights. Each turn, smash the two heaviest stones together. If they have equal weight, both are destroyed. If not, the smaller one is destroyed and the larger one’s weight is reduced by the smaller’s weight. Return the smallest possible weight of the remaining stone (or 0 if none remain).

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

Example 2: Input: stones = [31, 26, 33, 21, 40] Output: 5

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• 0/1 Knapsack — deciding which items to include up to a weight limit
• Subset Sum — can we partition values to hit a target sum?

1. Brute Force / Recursive

Intuition

Every stone ends up with either a + or - sign applied to it. The final result is the absolute value of sum(+group) - sum(-group). We want to minimise this difference. Try assigning each stone to either the positive or negative group recursively, then track the minimum absolute difference.

Algorithm

1. Define dfs(i, total) where total is the running signed sum so far.
2. Base case: when i == len(stones), return abs(total).
3. Try assigning +stones[i] and -stones[i], return the minimum result.

Solution

def lastStoneWeightII(stones):
    def dfs(i, total):
        if i == len(stones):
            return abs(total)
        return min(dfs(i + 1, total + stones[i]),
                   dfs(i + 1, total - stones[i]))

    return dfs(0, 0)


print(lastStoneWeightII([2, 7, 4, 1, 8, 1]))      # 1
print(lastStoneWeightII([31, 26, 33, 21, 40]))     # 5
print(lastStoneWeightII([1]))                       # 1

Complexity

• Time: O(2^n) — try both choices for each stone
• Space: O(n) — recursion depth

2. DP — Subset Sum / Knapsack

Intuition

The key insight: split stones into two groups A and B. The remaining weight is |sum(A) - sum(B)|. Since sum(A) + sum(B) = S (total), minimising |sum(A) - sum(B)| is equivalent to finding a subset with sum as close to S // 2 as possible. This reduces to a 0/1 knapsack: can we build a subset summing to each value from 0 to S // 2?

Build a boolean set dp of reachable sums. Start with {0}. For each stone, expand the set by adding stone to every existing reachable sum. After processing all stones, the answer is S - 2 * max(s for s in dp if s <= S // 2).

Algorithm

1. Compute S = sum(stones). Target = S // 2.
2. Initialise dp = {0} (set of reachable sums).
3. For each stone: dp = {s + stone for s in dp} | dp (but cap at target).
4. Find best = max(s for s in dp if s <= target).
5. Return S - 2 * best.

Solution

def lastStoneWeightII(stones):
    S = sum(stones)
    target = S // 2
    dp = {0}

    for stone in stones:
        new_dp = set()
        for s in dp:
            new_dp.add(s)
            if s + stone <= target:
                new_dp.add(s + stone)
        dp = new_dp

    best = max(dp)
    return S - 2 * best


print(lastStoneWeightII([2, 7, 4, 1, 8, 1]))      # 1
print(lastStoneWeightII([31, 26, 33, 21, 40]))     # 5
print(lastStoneWeightII([1]))                       # 1


# Alternative: boolean array version (classic knapsack style)
def lastStoneWeightII_v2(stones):
    S = sum(stones)
    target = S // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for stone in stones:
        # iterate backwards to avoid using same stone twice
        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 S - 2 * j

    return S


print(lastStoneWeightII_v2([2, 7, 4, 1, 8, 1]))   # 1
print(lastStoneWeightII_v2([31, 26, 33, 21, 40]))  # 5

Complexity

• Time: O(n * S) where S = sum(stones)
• Space: O(S)

Common Pitfalls

Iterating the knapsack dp forwards. When doing the 1D array approach, you must iterate j backwards. If you go forwards, a stone can be used multiple times (unbounded knapsack), which is wrong here.

Returning S // 2 - best. The answer is S - 2 * best, not S // 2 - best. We want the full difference between the two groups.

Assuming the answer is always 0. You can only make the difference zero if the stones are perfectly partitionable. In general, the best you can do is S mod 2 or larger.