Last Stone Weight II LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Bloomberg ByteDance Goldman Sachs GoogleViews 4181

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:

Test Case 1:

Input:

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

Output:

1

Explanation for Last Stone Weight II:

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

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

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

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

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

Approach

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.

Reference: https://en.wikipedia.org/wiki/Dynamic_programming

 

 

 

 

 

Translate »