# Last Stone Weight II LeetCode Solution

Difficulty Level Medium

## Problem Statement

The problem Last Stone Weight II  says 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, and
• 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 smallest possible weight of the left stone. If there are no stones left, return 0.

## Example for Last Stone Weight II Problem:

### Input:

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

1

## Explanation for Last Stone Weight II:

First, we can combine and to get 2, the array becomes [2, 7, 1, 8, 1].

Then we can combine and to get 1, the array becomes [2, 1, 1, 1].

We can combine and to get 1, then the array becomes [1, 1, 1].

We can combine and to get 0, the array becomes [1].

It is the last stone left. So the output is 1.

### Idea:

We can think of this problem as dividing the numbers into two subsets such that the minimum difference between the sum of two subsets will be minimum.

Let the 2 subsets be S1 and S2.

1. S1 + S2 = S
2. S1 – S2 = diff

==> diff = S – 2*S2 ==> minimize diff equals to maximize S2

So we have to find the maximum value of S2. We can use Dynamic Programming to solve this.

## Code

### Java Program for Last Stone Weight II LeetCode Solution

```class Solution {
public int lastStoneWeightII(int[] stones) {
int S = 0, S2 = 0;
for (int weight : stones)
S += weight;
int len = stones.length;
boolean[][] dp = new boolean[S + 1][len + 1];
for (int i = 0; i <= len; i++) {
dp[0][i] = true;
}
for (int i = 1; i <= len; i++) {
for (int s = 1; s <= S / 2; s++) {
if (dp[s][i - 1] || (s >= stones[i - 1] && dp[s - stones[i - 1]][i - 1])) {
dp[s][i] = true;
S2 = Math.max(S2, s);
}
}
}
return S - 2 * S2;
}
}```

### C++  Program for Last Stone Weight II LeetCode Solution

```class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(), stones.end(),0);
int minDiff = sum;
vector<bool> dp(sum+1, 0);
dp[0] = true;
for(auto x:stones) {
for (int i = dp.size()-1; i >=0; i--) {
if(dp[i])
dp[i+x] = true;
}
}
for(int i=0;i<dp.size();i++)
if(dp[i])
minDiff = min(minDiff, abs(i*2-sum));
return minDiff;
}
};```

## Complexity Analysis for Last Stone Weight II LeetCode Solution

### Time Complexity

The time complexity is O(n*sum), where n is the length of the array and sum is the sum of all the elements in the array.

### Space Complexity

The space complexity is O(sum)where the sum is the sum of all the elements in the array.

Translate »