Last Stone Weight II Interview Question for Google

You are given an array of integers stones where stones[i] is the weight of the i<sup>th</sup> 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 1:

stones = [2,7,4,1,8,1] Output: 1 Explanation: We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then, we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then, we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then, we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:

stones = [31,26,33,21,40] Output: 5

Constraints:

1 <= stones.length <= 30
1 <= stones[i] <= 100

Brute Force Solution

A naive approach would be to try all possible combinations of smashing stones together and keeping track of the minimum possible weight of the last stone. This can be achieved using recursion. The time complexity is exponential, specifically O(2^n), where n is the number of stones. This is because, at each step, we have a choice to smash a stone with any of the remaining stones.

Big O Time Complexity: O(2^n)

Big O Space Complexity: O(n) due to the recursive call stack.

Optimal Solution - Dynamic Programming

We can solve this problem more efficiently using dynamic programming. The key idea is to realize that the problem can be reframed as finding a subset of stones whose sum is closest to half of the total sum of all stones.

Calculate the Total Sum: Calculate the sum of all the stones.
Define DP Table: Create a DP table dp[i][j] which is a boolean value indicating whether a sum j can be achieved using the first i stones.
Base Case: dp[0][0] = true (a sum of 0 can always be achieved with no stones).
Iteration: Iterate through the stones and for each stone, update the DP table.
Result: After filling the DP table, find the largest sum j that can be achieved (i.e., dp[n][j] == true) and is less than or equal to totalSum / 2. The minimum possible weight of the last stone is totalSum - 2 * j. This works because we're trying to divide the stones into two groups with sums as close as possible, which is equivalent to finding a subset with a sum as close as possible to totalSum / 2.

Big O Time Complexity: O(n * sum), where n is the number of stones and sum is the total sum of the weights of the stones. Given the constraint that stone weights are between 1 and 100, and the max stones is 30, the sum will be at most 3000, so this is pseudo-polynomial.

Big O Space Complexity: O(n * sum) for the DP table.

Edge Cases

If the input array stones is empty, return 0.
If the input array stones has only one element, return the weight of that stone.

Code (Java)

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int totalSum = 0;
        for (int stone : stones) {
            totalSum += stone;
        }

        int n = stones.length;
        int target = totalSum / 2;

        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {
            int stone = stones[i - 1];
            for (int j = 0; j <= target; j++) {
                if (j < stone) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - stone];
                }
            }
        }

        int maxAchievedSum = 0;
        for (int j = target; j >= 0; j--) {
            if (dp[n][j]) {
                maxAchievedSum = j;
                break;
            }
        }

        return totalSum - 2 * maxAchievedSum;
    }
}