Last Stone Weight Ii - Leetcode Solution

Problem Statement:

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks 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 totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

Example:

Input: [2,7,4,1,8,1] Output: 1 Explanation: We can combine 2 and 4 to get 2, then combine 1 and 2 to get 1. The remaining stone has weight 1, so the answer is 1.

Solution:

To solve this problem, we will use the concept of dynamic programming.

First, we calculate the total sum of weights in the given input array. We will use this sum in the further steps.

Let's consider an array dp, where dp[i] denotes whether a weight i is possible or not. So, dp[0] will have a value of true, because a weight of 0 is always achievable. Initially, all other elements of dp will be false.

We iterate over the given input array stones. For each stone weight, we iterate over the dp array from its end to start. For each index j, we check if dp[j - stone] is true. If it is, then we can achieve a weight of j by either not picking this current stone or picking the stone and achieving weight j - stone.

We make dp[j] as true. Here, we need to iterate over the dp array from the end to start, because we do not want to include a stone twice.

Finally, we iterate over the second half of the dp array ( i.e. dp[sum/2 + 1] to dp[sum]) to check for the smallest possible weight. The first index with a value of true will be the answer.

Code:

Here is the Python3 code to solve the problem.

def lastStoneWeightII(stones: List[int]) -> int:
    total_sum = sum(stones)
    dp = [False for _ in range(total_sum//2 + 1)]
    dp[0] = True
    for stone in stones:
        for j in range(total_sum//2, -1, -1):
            if j - stone >= 0 and dp[j - stone]:
                dp[j] = True

    for i in range(total_sum//2, -1, -1):
        if dp[i]:
            return total_sum - 2*i
    return 0

1