Last Stone Weight II

Last Stone Weight II

1. What is this problem about?

Last Stone Weight II is significantly more complex than the first version. You are still smashing stones together, but you want to find the smallest possible weight of the last remaining stone. This means you can choose the order and pairings of smashes to minimize the final outcome.

2. Why is this asked in interviews?

Amazon and Google ask this "Medium" problem to test a candidate's ability to transform a physical simulation into a classic dynamic programming problem. It requires the insight that minimizing the last stone's weight is equivalent to partitioning the stones into two groups such that the difference between their total weights is minimized. This is a variation of the well-known "Knapsack" or "Subset Sum" problem.

3. Algorithmic pattern used

This utilizes the Dynamic Programming interview pattern. Specifically, it's a 0/1 Knapsack variation. We want to find a subset of stones whose sum is as close to total_sum / 2 as possible. If the sum of one subset is S, the sum of the other is total_sum - S, and their difference (the final stone weight) is (total_sum - S) - S = total_sum - 2S. We use a boolean DP array where dp[i] is true if a sum i is achievable.

4. Example explanation

Stones: [2, 3, 5]. Total sum = 10. Target = 10 / 2 = 5.

1. Can we form sum 5? Yes (using {5} or {2, 3}).
2. Max achievable sum S <= 5 is 5.
3. Result = 10 - 2 * 5 = 0. If stones were [2, 4, 5], total sum = 11, target = 5.5.
4. Max achievable sum S <= 5 is 5.
5. Result = 11 - 2 * 5 = 1.

5. Common mistakes candidates make

The most common mistake is trying to use a greedy approach (like the first Last Stone Weight problem), which does not work here. Another error is failing to recognize the relationship between this problem and the Subset Sum problem. Some candidates also struggle with the memory limits and should use a 1D DP array to optimize space complexity.

6. Interview preparation tip

For "Array, Dynamic Programming interview pattern" questions, always try to reduce the problem to a known classic. If the problem involves partitioning or choosing subsets, Knapsack and Subset Sum should be the first things you consider.