1049. Last Stone Weight II

Problem Description

The problem involves a game played with a collection of stones, each with a certain weight. During the game, two stones are picked in every turn and smashed against each other. If the weights of the stones are equal (x == y), both stones are destroyed. If they are not (x != y), the lighter stone is destroyed and the heavier stone's weight is reduced by the weight of the lighter stone. The aim of the game is to minimize the weight of the last remaining stone after all turns have been played. If no stones remain, the weight is considered to be 0.

Intuition

To solve this problem, we can think of it in terms of a 0/1 Knapsack problem, a common strategy used in dynamic programming. In the 0/1 Knapsack problem, we aim to maximize the value of items that can be fit into a knapsack of limited capacity without exceeding the weight limit.

For this game, we can imagine having a "knapsack" with a capacity that is half the sum of all stone weights. The reason we use half the sum is that we seek to partition the stones into two groups that are as equal in total weight as possible. By doing so, when the stones from these groups battle each other, the resulting stone (if any) will have the minimal possible weight.

So, we construct a dynamic programming array dp where dp[j] keeps the maximum achievable sum of stones that does not exceed the capacity j. We iterate over each stone and update the dp array, considering the current stone to either be included or excluded from our "knapsack". Eventually, dp[-1] will contain the largest weight that is less than or equal to the sum of all stones divided by two.

The smallest possible weight of the final stone can then be calculated as the total weight of all stones minus twice the weight indicated by dp[-1], because for every weight we put in one group, we are effectively removing it from what would be the opposing group of stones in the "game".

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming to solve this modified knapsack problem. Here's a step-by-step walkthrough of the implementation:

Calculate the sum s of all stones. The objective is to partition the stones into two groups with a total weight that is as close to s / 2 as possible.
Define n as s / 2 because this represents the largest possible weight our "knapsack" may store. Since we only need an integer knapsack weight, we use a bitwise right shift s >> 1, equivalent to s / 2 but faster computationally.
Initialize a dynamic programming array dp of size n + 1 with zeros. This array will help us to keep track of the maximum weight that can be achieved for each capacity up to n. dp[j] will represent the maximum weight that can be accumulated with a knapsack capacity of j.
The outer loop goes through each stone's value v in the stones array.
The inner loop is a reversed loop from n to v. This loop updates the dp array. For each capacity j from n down to the weight of the current stone v, we check whether including the stone would lead to a better result compared to not including it.
Within the inner loop, the expression dp[j] = max(dp[j], dp[j - v] + v) updates the current dp[j] value. It evaluates two situations: not taking the current stone (leaving dp[j] as it is) or taking the stone (which would be dp[j - v] + v). If the latter offers a higher weight without exceeding the capacity j, we update dp[j].
After filling the dp array, the maximum sum we can get from one group of stones is dp[-1]. The smallest possible weight of the last remaining stone is then s - dp[-1] * 2. We subtract double dp[-1] from the total sum s because, effectively, for every stone placed in one group, we remove that weight from the potential remaining stone.

By using dynamic programming, this solution efficiently determines the best way to "pack" the stones into two groups with the goal of minimizing the weight of the last remaining stone after all possible smashes.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach with a stones array stones = [2,7,4,1,8,1].

We first calculate the sum s of all stones, which is 2 + 7 + 4 + 1 + 8 + 1 = 23. The goal is to partition the stones into two groups with a total weight that is as close to s / 2 = 23 / 2 = 11.5 as possible for minimizing the last stone's weight.
We define n as the integer part of s / 2, which gives us n = 11 since we're dealing with integer weights.
We initialize a dynamic programming array dp of size n + 1 with zeros: dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], corresponding to knapsack capacities from 0 to 11.
We start iterating through the stones array:
- For stone value v = 2, we update dp from end to start where j >= v.
- For stone value v = 7, we repeat the updating process.
- We continue until all stones are considered.
For the first iteration with v = 2, the inner loop will check capacities from 11 down to 2. The update looks like:
- For j = 11, we consider including the stone or not: dp[11] = max(dp[11], dp[11 - 2] + 2).
- For j = 10, decide between dp[10] and dp[10 - 2] + 2.
- And so on, down to j = 2.
After we process v = 2, the dp array changes indicating the best way to pack stones up to now: dp = [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
We process all stones this way, and the dp array continues to update with the maximum weights for each capacity.
At the end, assuming after all updates our dp array looks like: dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
The maximum sum we can get from one group of stones is dp[-1] which is 11. This means that one group of stones has a total weight of 11, and so does the second group, as we wanted two equal groups.
The smallest possible weight of the last remaining stone is then s - dp[-1] * 2 = 23 - 11 * 2 = 1.

So, the algorithm leads to the partitioning of the stones into two groups whose weights differ by at most 1. The weight of the last stone—if any—is minimized, which in this case is 1, as this is the least weight we can achieve by using dynamic programming and the knapsack analogy.

Solution Implementation

1from typing import List
2
3class Solution:
4    def lastStoneWeightII(self, stones: List[int]) -> int:
5        # Calculate the sum of all stones
6        total_weight = sum(stones)
7        # Calculate the maximum possible weight that can be reached by any subset of stones
8        max_possible_weight = total_weight >> 1
9      
10        # Initialize the dynamic programming table with zeros. The table will have 'max_possible_weight + 1' elements.
11        dp = [0] * (max_possible_weight + 1)
12      
13        # Iterate over each stone in the input list
14        for stone in stones:
15            # Update the dynamic programming table in reverse order.
16            # This ensures that each stone is only used once when calculating the maximum sum for each subset.
17            for current_weight in range(max_possible_weight, stone - 1, -1):
18                # At each position, we want to take the maximum between:
19                # (the current value at dp[current_weight]) and (the value at dp[current_weight - stone] + stone)
20                # This represents either not taking the current stone or taking it and adding its weight to the subset.
21                dp[current_weight] = max(dp[current_weight], dp[current_weight - stone] + stone)
22      
23        # The final answer is the difference between the total weight and twice the weight of one of the subsets
24        # This is because the other subset will have a total weight of `total_weight - dp[-1]`, resulting in the minimum possible difference.
25        return total_weight - dp[-1] * 2
26

1class Solution {
2    public int lastStoneWeightII(int[] stones) {
3        // Calculate the sum of all stones' weights
4        int sumOfStones = 0;
5        for (int weight : stones) {
6            sumOfStones += weight;
7        }
8
9        // The number of stones in the array
10        int numOfStones = stones.length;
11      
12        // Set the target as half of the sum, because we are trying
13        // to minimize the difference between two groups to get the
14        // smallest last stone weight possible
15        int target = sumOfStones >> 1; // Equivalent to sumOfStones / 2
16
17        // Initialize a DP array where dp[i] will store the maximum
18        // weight that can be achieved with a sum not exceeding i
19        int[] dp = new int[target + 1];
20
21        // Loop through each stone
22        for (int weight : stones) {
23            // Update dp array in a reverse manner to ensure that
24            // each stone is only used once
25            for (int j = target; j >= weight; --j) {
26                // Determine whether to include the current stone or not
27                // by comparing which choice gives us a higher weight
28                // that does not exceed the current weight limit j
29                dp[j] = Math.max(dp[j], dp[j - weight] + weight);
30            }
31        }
32
33        // The result is the difference between the sum of all stones
34        // and twice the weight of the heavier group
35        // This is because we are trying to partition the array into
36        // two groups such that the difference between the sum of two groups
37        // is minimized (typical partition problem that can be solved by DP).
38        return sumOfStones - dp[target] * 2;
39    }
40}
41

1#include <vector>
2#include <numeric>
3using namespace std;
4
5class Solution {
6public:
7    int lastStoneWeightII(vector<int>& stones) {
8        // Calculate the sum of all stone weights
9        int totalWeight = accumulate(stones.begin(), stones.end(), 0);
10        // Target weight is to try splitting stones into two groups with equal weight
11        int targetWeight = totalWeight >> 1;
12        // Initialize a DP array to store maximum achievable weight for each possible weight up to targetWeight
13        vector<int> dp(targetWeight + 1, 0);
14
15        // DP approach to find the closest sum to the targetWeight
16        for (int stone : stones) {  // for each stone
17            // Traverse dp array backwards for this pass, to avoid using a stone twice
18            for (int j = targetWeight; j >= stone; --j) {
19                // Update dp[j] to the higher of the two values;
20                // either the current dp[j] or the sum of stone and dp[j - stone] if we include the stone
21                dp[j] = max(dp[j], dp[j - stone] + stone);
22            }
23        }
24
25        // The answer is the total weight minus twice the optimized closest sum to half of the total weight
26        // This represents the minimal possible weight difference between two groups
27        return totalWeight - dp[targetWeight] * 2;
28    }
29};
30

1/**
2 * Solves the Last Stone Weight II problem using dynamic programming.
3 * The function calculates the minimum possible weight difference
4 * between two groups into which the stones can be divided.
5 *
6 * @param {number[]} stones An array of integers representing stones' weights.
7 * @return {number} The minimum possible weight difference between two groups.
8 */
9function lastStoneWeightII(stones: number[]): number {
10    // Calculate the sum of all stones.
11    let sum = stones.reduce((acc, v) => acc + v, 0);
12
13    // Calculate half of the sum as the target sum for one subset.
14    const target = sum >> 1;
15
16    // Initialize the dp array with zeros for storing the maximum sum possible for each subset sum.
17    let dp: number[] = new Array(target + 1).fill(0);
18
19    // Update the dp array to find the maximum subset sum less than or equal to half the total sum.
20    for (let stone of stones) {
21        for (let j = target; j >= stone; --j) {
22            dp[j] = Math.max(dp[j], dp[j - stone] + stone);
23        }
24    }
25
26    // The result is the total sum minus twice the maximum subset sum
27    // which gives the smallest possible difference.
28    return sum - dp[target] * 2;
29}
30
31// Example usage:
32// const stones = [2, 7, 4, 1, 8, 1];
33// const result = lastStoneWeightII(stones);
34// console.log(result); // Output should be the minimum possible weight difference
35

Time and Space Complexity

The given code is an implementation of a dynamic programming solution to solve a variation of the classic knapsack problem. To analyze the time complexity and space complexity, let us explore the code:

Time Complexity

The time complexity of the code can be determined by looking at the nested loops. There is an outer loop that iterates over each stone, and an inner loop that runs in reverse from "n" (where "n" is half of the sum of stones, "s >> 1") to the value of the current stone "v" (i.e., "range(n, v - 1, -1)"). The inner loop ensures that each sub-sum only considers each stone once.

The outer loop runs once for each stone, so it runs "m" times where "m" is the number of stones ("len(stones)").
The inner loop runs (at most) "n" times for each outer iteration, where "n" is half the sum of all stone weights, rounded down ("s >> 1").

Therefore, the overall time complexity is O(mn), where "m" is the number of stones and "n" is half the sum of the stones' weights.

Space Complexity

The space complexity of the code is determined by the storage requirements. The array "dp" of size "n + 1" is created to store the maximum achievable weight for each sub-sum. No other data structures are used that grow with the size of the input. Thus, the space complexity is O(n), where "n" is half the sum of the stones' weights.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: