1049. Last Stone Weight II - Leetcode Solution

Code Implementation

class Solution:
    def lastStoneWeightII(self, stones):
        total = sum(stones)
        target = total // 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]
        for i in range(target, -1, -1):
            if dp[i]:
                return total - 2 * i

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = accumulate(stones.begin(), stones.end(), 0);
        int target = total / 2;
        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 total - 2 * i;
        }
        return 0;
    }
};

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int s : stones) total += s;
        int target = total / 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];
            }
        }
        for (int i = target; i >= 0; --i) {
            if (dp[i]) return total - 2 * i;
        }
        return 0;
    }
}

var lastStoneWeightII = function(stones) {
    let total = stones.reduce((a, b) => a + b, 0);
    let target = Math.floor(total / 2);
    let dp = new Array(target + 1).fill(false);
    dp[0] = true;
    for (let stone of stones) {
        for (let i = target; i >= stone; --i) {
            dp[i] = dp[i] || dp[i - stone];
        }
    }
    for (let i = target; i >= 0; --i) {
        if (dp[i]) return total - 2 * i;
    }
    return 0;
};

Problem Description

You are given an array stones where each element represents the weight of a stone. In each turn, you can choose any two stones and smash them together. If the stones have equal weight, both are destroyed. If they have different weights, the stone with the larger weight is replaced by the difference, and the smaller one is destroyed. This process repeats until there is at most one stone left. Your task is to return the smallest possible weight of the remaining stone (or 0 if all stones are destroyed).

Key points:

You must use each stone exactly once.
You can choose any two stones at each step.
Return the minimal possible final weight after all possible smash operations.

Thought Process

At first glance, the problem seems to require simulating all possible ways to smash stones together, which could be very complex. However, if we think about the process, smashing two stones is equivalent to splitting stones into two groups and minimizing the absolute difference between their total weights. This is because, after all smashes, the leftover stone (if any) will have a weight equal to the difference between the sums of the two groups.

The brute-force approach would be to try all possible ways to partition the stones into two groups and compute the difference, but this quickly becomes infeasible as the number of stones grows. We need a more efficient way to find the most balanced partition.

Solution Approach

To solve this problem efficiently, we can use dynamic programming, similar to the classic "subset sum" problem:

Let total be the sum of all stones.
We want to split the stones into two groups whose sums are as close as possible. Let the sum of one group be sum1, and the other sum2 = total - sum1.
The final answer will be abs(sum1 - sum2) = abs(total - 2 * sum1).
Our goal is to find the largest sum1 less than or equal to total // 2 that can be formed by selecting a subset of stones.
We use a boolean dynamic programming array dp of size target + 1 (where target = total // 2), where dp[i] is true if a subset sum of i can be formed.
For each stone, we update the dp array from high to low to avoid using the same stone multiple times.
Finally, we find the largest i where dp[i] is true and return total - 2 * i as the answer.

Example Walkthrough

Suppose stones = [2,7,4,1,8,1].

Total sum = 23
Target = 11 (since 23 // 2 = 11)
We want the largest subset sum ≤ 11.
Using dynamic programming, we find that 11 is achievable (e.g., 2+4+1+1+3=11).
So, the minimal remaining weight is 23 - 2*11 = 1.
This matches the optimal way of smashing stones: after all operations, the smallest possible leftover is 1.

This process ensures we always find the best possible partition of stones.

Time and Space Complexity

Brute-force approach: The number of ways to partition n stones is 2^n, so time complexity is exponential and infeasible for large n.
Optimized DP approach: For n stones and total sum S, time complexity is O(n * S/2) since for each stone, we process up to S/2 subset sums. Space complexity is O(S/2) for the DP array.
This is efficient enough for the constraints of the problem (stones' weights ≤ 100, number of stones ≤ 30).

Summary

The key insight is to reframe the problem from simulating every possible smash to partitioning the stones into two groups with minimal difference in their sums. Using dynamic programming, we efficiently find the closest possible subset sum to half the total, ensuring the smallest possible leftover stone. This approach is both elegant and efficient, transforming a seemingly complex simulation into a classic subset-sum problem.

AlgoMap.io

Want Help Cracking FAANG?