Last Stone Weight II
Problem Description
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 weightxis destroyed, and the stone of weightyhas new weighty - 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:
Input: 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:
Input: stones = [31,26,33,21,40]
Output: 5
Constraints:
1 <= stones.length <= 301 <= stones[i] <= 100
Solve it on LeetCode
Approaches
1. Recursion
Intuition:
The problem can be reduced to a classic "Partition problem" where we need to split the stones into two groups such that their absolute difference in sum is minimized. A recursive approach involves dividing the set of stones into subsets and calculating their possible weights. The main recursive function attempts to either include or exclude a stone in a possible "bucket" or subset and recursively attempts to minimize the difference between two subsets.
Steps:
- Calculate half of the total weight of all stones (
sum/2). - Define a recursive function that tries to reach a sum as close to
halfas possible from available stones. - Base case: If no more stones are left, return the absolute difference between
2*currentSubsetSumandtotalSum. - For each stone, make an include/exclude decision and recursively compute the answer.
Code:
- Time Complexity: O(2^n) where
nis the number of stones. The recursive function potentially explores all subsets of stones. - Space Complexity: O(n) due to the recursion stack space.
2. Dynamic Programming
Intuition:
To improve upon our recursive method, we can utilize a dynamic programming approach similar to solving the subset sum problem. Our task is to find a subset of stones whose sum is as close as possible to sum/2. Using a DP table, we can keep track of the maximum possible sum of stone weights that can be achieved.
Steps:
- Calculate
half = totalSum / 2: our goal is to find a sum as close as possible tohalf. - Use a DP array
dpwheredp[j]will maintain whether a sumjcan be achieved with available stones. - Initialize
dp[0] = truesince a sum of zero can always be achieved without including any stone. - Iterate over each stone, and for each stone, iterate over all possible sums from
halfto the stone weight in reverse, updating the DP array. - Look for the largest
jsuch thatdp[j]istrue. The result will betotalSum - 2*j.
Code:
- Time Complexity: O(n * {sum / 2}), where
nis the number of stones andsumis the total sum of stones. - Space Complexity: O({sum / 2})) due to the DP array.