Last Stone Weight II

Problem Description

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x ≤ y. The result of this smash is:

• If x == y, both stones are destroyed,
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the minimum possible weight of the left stone. If there are no stones left, return 0.

Examples

Constraints

• 1 ≤ stones.length ≤ 30
• 1 ≤ stones[i] ≤ 100

Reduce to Partitioning into Two Subsets

Smashing stones together repeatedly is mathematically equivalent to partitioning the stones into two groups, Group A (positive signs) and Group B (negative signs), such that the difference between their sums is minimized.

Let the total sum of all stones be totalSum. We want to find a subset of stones that sums to S such that S is as close as possible to totalSum / 2 (without exceeding it). Once we find the maximum possible sum S that can be formed using a subset of stones:

• The sum of the other group will be totalSum - S.
• The minimum difference (remaining stone weight) will be (totalSum - S) - S = totalSum - 2 * S.

This reduces exactly to the 0/1 Knapsack problem / Subset Sum (similar to Partition Equal Subset Sum).

Solution: 1D DP Array

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int totalSum = 0;
        for (int s : stones) totalSum += s;

        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int stone : stones) {
            for (int i = target; i >= stone; i--) {
                dp[i] = dp[i] || dp[i - stone];
            }
        }

        // find the largest sum S <= target that can be formed
        for (int i = target; i >= 0; i--) {
            if (dp[i]) {
                return totalSum - 2 * i;
            }
        }

        return 0;
    }
}

class Solution:
    def lastStoneWeightII(self, stones: list[int]) -> int:
        total_sum = sum(stones)
        target = total_sum // 2

        dp = [False] * (target + 1)
        dp[0] = True

        for stone in stones:
            for i in range(target, stone - 1, -1):
                dp[i] = dp[i] or dp[i - stone]

        # find the largest sum <= target
        for i in range(target, -1, -1):
            if dp[i]:
                return total_sum - 2 * i

        return 0

#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
public:
    int lastStoneWeightII(std::vector<int>& stones) {
        int totalSum = std::accumulate(stones.begin(), stones.end(), 0);
        int target = totalSum / 2;

        std::vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int stone : stones) {
            for (int i = target; i >= stone; i--) {
                dp[i] = dp[i] || dp[i - stone];
            }
        }

        for (int i = target; i >= 0; i--) {
            if (dp[i]) {
                return totalSum - 2 * i;
            }
        }

        return 0;
    }
};

Complexity Analysis:

• Time Complexity: O(N * S) where N is the number of stones and S is total_sum / 2. Max stones is 30, max weight is 100, so total_sum ≤ 3000 and S ≤ 1500. The nested loop runs at most 30 * 1500 = 45000 iterations, which is extremely fast.
• Space Complexity: O(S) to store the 1D DP array.

← All Problems