Leetcode 1049. Last Stone Weight II

Problem Explanation:

The problem is derived from a common problem of collecting rocks of different positive integer weights. During each turn, we select two stones and smash them together. The weights of the selected rocks are described by x and y (x <= y). Depending on the result of the collision:

• If x == y: both stones are completely obliterated.
• If x != y: the stone of weight x is completely obliterated, but the stone of weight y has its weight reduced to y-x.

Ultimately, we can have at most one stone remaining. The aim is to discover the smallest possible weight of this remaining stone. If no stones are left, the weight is 0.

Example:

Let's consider an example with input, stones = [2,7,4,1,8,1]

We can start by combining stones weighing 2 and 4. The weight will be reduced to 2 (since 4 - 2 = 2). So the new array of stone weights will be [2,7,1,8,1].

Next, we can combine stones weighing 7 and 8. The weight will reduced to 1 (since 8 - 7 = 1). So the new array of stone weights will be [2,1,1,1].

After that, we can smash stones weighing 2 and 1. The weight will reduced to 1 (since 2 - 1 = 1). So the new array of stone weights will be [1,1,1].

Lastly, we can combine two stones weighing 1 each. The weight will reduced to 0 (since 1 - 1 = 0). So the new array of stone weights will be [1].

So the smallest possible weight of the final stone is 1 which is the output.

Solution Approach:

This problem can be solved by dynamic programming. It can be translated into a subset problem through a change of perspective and then solved by dynamic programming methodologies. You construct a dp array that contains the sum/2 possible weights. From your given stones array, you fill up the dp array to build all possible weights and keep track of the heaviest weight (s) you can make that is less or equal to half of the total weight.

Python Solution:

1
2python
3# Importing the library functools
4import functools
5
6class Solution:
7    def lastStoneWeightII(self, stones: List[int]) -> int:
8        # calculating possible weights by looping through the stones
9        dp = {0}
10        for stone in stones:
11            dp |= {stone + i for i in dp}
12        total_weight = sum(stones)
13        # returning the minimum difference of total weight and twice the maximum possible weight less than half total weight
14        return min(total_weight - i * 2 for i in dp if total_weight - i >= i)

Java Solution:

1
2java
3class Solution {
4    public int lastStoneWeightII(int[] stones) {
5        boolean[] dp = new boolean[1501];
6        dp[0] = true;
7        int sumWeight = 0;
8        for (int weight : stones) {
9            sumWeight += weight;
10            for (int i = Math.min(1500, sumWeight); i >= weight; --i) {
11                dp[i] = dp[i] || dp[i - weight];
12            }
13        }
14        for (int i = sumWeight / 2; i >= 0; --i)
15            if (dp[i]) return sumWeight - i * 2;
16        return 0;
17    }
18}
19

Javascript Solution:

1
2javascript
3var lastStoneWeightII = function(stones) {
4    const dp = new Uint8Array(1501);
5    dp[0] = 1;
6    let sum = 0;
7    for (let i = 0; i < stones.length; i++) {
8        sum += stones[i];
9        for (let j = Math.min(sum, 1500); j >= stones[i]; j--)
10            dp[j] |= dp[j - stones[i]];
11    }
12    for (let i = sum >> 1; ; i--) 
13        if (dp[i]) return sum - (i * 2);    
14};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int lastStoneWeightII(vector<int>& stones) {
6        bitset<1501> dp = {1};
7        int sum = 0, res = 0;
8        for (int weight : stones) sum += weight, dp |= dp << weight;
9        for (res = sum / 2; sum - res * 2 < res; res--) if (dp[res]) break;
10        return sum - res * 2;
11    }
12};

C# Solution:

1
2csharp
3public class Solution {
4    public int LastStoneWeightII(int[] stones) {
5        bool[] dp = new bool[1501];
6        dp[0] = true;
7        int sumWeight = 0;
8        foreach (int weight in stones) {
9            sumWeight += weight;
10            for (int i = Math.Min(sumWeight, 1500); i >= weight; --i) {
11                dp[i] = dp[i] || dp[i - weight];
12            }
13        }
14        for (int i = sumWeight / 2; i >= 0; --i) {
15            if (dp[i]) return sumWeight - i * 2;
16        }
17        return 0;
18    }
19}

All the solutions given in different programming languages follow the same approach as explained in the approach section. They first calculate the total weight of all stones then by looping through the stone weights, they keep updating the possible weights. Then check the minimum difference between total weight and maximum possible weight (less than half of the total weight).This approach works because it essentially treats the problem as a partitioning problem, where we are dividing the stones into two groups with the smallest difference possible. By considering all combinations (subsets) of the stones and tracking which sums are possible, we are able to find the largest sum that is less than or equal to half of the total weight of all stones. The final result is obtained by calculating the difference of this sum with the total weight.

The performance of the solution depends on the implementation and programming language, but in most cases, it runs relatively efficiently because it takes advantage of characteristics of the problem (particularly, the limited range of stone's weights).

It is also important to note that although the solution uses a dynamic programming approach, it could also be seen as a variation of the knapsack problem: we want to pack many different weights (the stones) into a bag of limited capacity (half of the total weight), maximizing the total weight packed in. Here, instead of trying to maximize the value of items, we try to maximize weight, making it closer to half the total weight, so the remaining weight (which is also the remaining stone) is as small as possible.

The complexity of the algorithm is O(n^2) because for each stone we need to check all previously computed sums, where n is the length of the stones array. The space complexity is linear - we only need a boolean array dp with a length equal to the half of the total sum of stones.

Before starting the problem, it’s very crucial to understand the question very well and the above approach should give you a clear outlook to solve similar dynamic programming problems.