Problem Description

You have a collection of stones, each with a specific weight given in an array stones, where stones[i] represents the weight of the i-th stone.

You're playing a stone-smashing game with the following rules:

• On each turn, you select any two stones and smash them together
• If you pick two stones with weights x and y (where x ≤ y):
  • When x == y: Both stones are completely destroyed
  • When x != y: The lighter stone (weight x) is destroyed, and the heavier stone (weight y) becomes a new stone with weight y - x

The game continues until you have at most one stone remaining.

Your goal is to find the minimum possible weight of the final remaining stone. If no stones remain at the end, return 0.

For example, if you have stones [2, 7, 4, 1, 8, 1]:

• One possible sequence: smash 2 and 4 → get 2, smash 7 and 8 → get 1, smash 1 and 1 → get 0, smash 2 and 1 → get 1, final result is 1
• The optimal strategy would minimize this final weight

The solution uses dynamic programming to solve this as a subset sum problem. The key insight is that smashing stones is equivalent to partitioning them into two groups and finding the minimum difference between the groups' sums. The DP approach finds the maximum sum possible that doesn't exceed half of the total sum, then calculates the minimum difference as total_sum - 2 * max_subset_sum.

Intuition

Let's think about what happens when we smash stones together. When we smash stones with weights x and y, we get a new stone with weight |x - y|. This is essentially subtracting one weight from another.

If we trace through the entire game, we can observe that each stone in the original array will eventually contribute to the final result with either a positive or negative sign. For instance, if we have stones [a, b, c, d], the final result could be something like a - b + c - d or a + b - c - d, depending on how we pair and smash them.

This means we're essentially trying to divide the stones into two groups: one group gets a positive sign and the other gets a negative sign. The final weight will be the absolute difference between the sums of these two groups.

To minimize the final stone weight, we want to minimize |sum(group1) - sum(group2)|. This is equivalent to partitioning the stones into two subsets with sums as close to each other as possible.

If the total sum is S, and one subset has sum subset_sum, then the other subset has sum S - subset_sum. The difference between them is |(S - subset_sum) - subset_sum| = |S - 2 * subset_sum|.

To minimize this difference, we want subset_sum to be as close to S/2 as possible. The problem now transforms into: "Find the maximum sum of a subset that doesn't exceed S/2."

This is a classic 0/1 knapsack problem where:

• The "capacity" of our knapsack is S/2
• Each stone can either be included in our subset (put in knapsack) or not
• We want to maximize the sum without exceeding S/2

Once we find this maximum possible subset_sum, the minimum final stone weight is S - 2 * subset_sum.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a dynamic programming approach to solve the 0/1 knapsack problem we identified in our intuition.

Setup:

• Calculate the total sum s of all stones
• Set the target capacity as n = s >> 1 (which is s // 2)
• Create a 2D DP table dp[m+1][n+1] where m is the number of stones

DP Table Definition:

• dp[i][j] represents the maximum sum we can achieve using the first i stones with a capacity limit of j
• The table has dimensions (m+1) × (n+1) to handle the base case where we use 0 stones

DP Transition: For each stone i (from 1 to m) and each capacity j (from 0 to n):

1. Option 1 - Don't take the current stone:

   • dp[i][j] = dp[i-1][j]
   • We inherit the best result from considering the first i-1 stones

2. Option 2 - Take the current stone (if it fits):

   • Only possible if stones[i-1] <= j (the stone's weight doesn't exceed current capacity)
   • If we take it: dp[i][j] = dp[i-1][j - stones[i-1]] + stones[i-1]
   • This means we add the stone's weight to the best result we could get with remaining capacity

3. Choose the maximum:

   • dp[i][j] = max(Option 1, Option 2)

Building the Solution: The algorithm fills the DP table row by row:

for i in range(1, m + 1):
    for j in range(n + 1):
        dp[i][j] = dp[i - 1][j]  # Don't take stone i
        if stones[i - 1] <= j:    # Can we take stone i?
            dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1])

Final Answer:

• dp[-1][-1] (or dp[m][n]) gives us the maximum sum of a subset that doesn't exceed s/2
• This represents one group of stones with sum closest to half the total
• The other group has sum s - dp[m][n]
• The minimum difference is: (s - dp[m][n]) - dp[m][n] = s - 2 * dp[m][n]

Time Complexity: O(m * n) where m is the number of stones and n is half the total sum Space Complexity: O(m * n) for the DP table

Example Walkthrough

Let's walk through the solution with stones = [2, 7, 4, 1, 8, 1].

Step 1: Calculate total sum and target

• Total sum s = 2 + 7 + 4 + 1 + 8 + 1 = 23
• Target capacity n = 23 // 2 = 11
• We want to find the maximum subset sum ≤ 11

Step 2: Initialize DP table

• Create dp[7][12] (6 stones + 1, capacity 0 to 11)
• Initialize first row to 0 (using 0 stones gives sum 0)

Step 3: Fill DP table

Let's trace through key decisions:

For stone 1 (weight = 2):

• At capacity j=2: Can take stone → dp[1][2] = 2
• At capacity j=3: Can take stone → dp[1][3] = 2
• Continue for all capacities...

For stone 2 (weight = 7):

• At capacity j=7: Can take stone → dp[2][7] = 7
• At capacity j=9: Can take stone 2 alone (7) or stones 1+2 (2+7=9) → dp[2][9] = 9
• At capacity j=11: Best is stones 1+2 → dp[2][11] = 9

For stone 3 (weight = 4):

• At capacity j=6: Can take stones 1+3 (2+4=6) → dp[3][6] = 6
• At capacity j=11: Can take stones 2+3 (7+4=11) or keep previous best (9) → dp[3][11] = 11

For stone 4 (weight = 1):

• At capacity j=8: Can add stone 4 to previous combinations → dp[4][8] = 8
• At capacity j=11: Previous best was already 11 → dp[4][11] = 11

For stone 5 (weight = 8):

• At capacity j=10: Can take stones 1+5 (2+8=10) → dp[5][10] = 10
• At capacity j=11: Can take stones 1+4+5 (2+1+8=11) or keep 11 → dp[5][11] = 11

For stone 6 (weight = 1):

• At capacity j=11: Already at maximum → dp[6][11] = 11

Step 4: Calculate result

• Maximum subset sum ≤ 11 is dp[6][11] = 11
• One group has sum 11, the other has sum 23 - 11 = 12
• Minimum stone weight = 23 - 2×11 = 23 - 22 = 1

The final DP table (showing key columns):

       j=0  j=2  j=4  j=6  j=7  j=9  j=10  j=11
i=0     0    0    0    0    0    0     0     0
i=1(2)  0    2    2    2    2    2     2     2
i=2(7)  0    2    2    2    7    9     9     9
i=3(4)  0    2    4    6    7    9     9    11
i=4(1)  0    2    4    6    7    9    10    11
i=5(8)  0    2    4    6    7    9    10    11
i=6(1)  0    2    4    6    7    9    10    11

This gives us the minimum possible final stone weight of 1, which matches the expected result!

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of stones and n is half of the total sum of all stones.

The algorithm uses a nested loop structure:

• The outer loop iterates through all stones from 1 to m, giving us O(m) iterations
• The inner loop iterates from 0 to n (where n = sum(stones) / 2), giving us O(n) iterations for each stone
• Inside the nested loops, all operations (comparisons, assignments, array accesses) are O(1)
• Therefore, the overall time complexity is O(m * n)

Since n can be at most O(m * max(stones)) in the worst case (where all stones have the maximum value), the time complexity can also be expressed as O(m * sum(stones) / 2) or simply O(m * S) where S is the sum of all stone weights.

Space Complexity: O(m * n) where m is the number of stones and n is half of the total sum.

The space complexity is dominated by:

• The 2D DP table dp with dimensions (m + 1) × (n + 1), requiring O(m * n) space
• The input list stones is given as input and not counted in auxiliary space
• A few constant variables (s, m, n, loop counters) requiring O(1) space
• Therefore, the overall space complexity is O(m * n)

This can be optimized to O(n) space by using a 1D DP array since each row only depends on the previous row, but the current implementation uses the full 2D table.

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

Common Pitfalls

1. Integer Overflow with Large Stone Weights

When calculating the total sum, if individual stone weights are large (near the constraint limits), the sum might cause issues in some languages. In Python this is handled automatically, but in languages like Java or C++, you might need to use appropriate data types.

Solution: Use long or appropriate large integer types when calculating sums in statically-typed languages.

2. Incorrect DP Table Indexing

A frequent mistake is confusing the indexing between stones array and DP table. Since DP table uses 1-based indexing for stones (row 0 represents using 0 stones), but the stones array uses 0-based indexing, accessing stones[i] when filling dp[i][j] is wrong.

Incorrect:

if stones[i] <= j:  # Wrong! Off-by-one error
    dp[i][j] = max(dp[i][j], dp[i-1][j - stones[i]] + stones[i])

Correct:

if stones[i-1] <= j:  # Correct! Account for different indexing
    dp[i][j] = max(dp[i][j], dp[i-1][j - stones[i-1]] + stones[i-1])

3. Using Full Sum Instead of Half

Some might create a DP table with the second dimension as total_sum instead of total_sum // 2. This wastes memory and computation since we only need to find subsets up to half the total.

Solution: Always use target = total_sum // 2 as the capacity limit.

4. Space Optimization Pitfall

When optimizing space to use a 1D array instead of 2D, iterating forward through capacities will cause incorrect results due to overwriting values needed for computation.

Incorrect 1D optimization:

dp = [0] * (target + 1)
for stone in stones:
    for j in range(target + 1):  # Wrong! Forward iteration
        if stone <= j:
            dp[j] = max(dp[j], dp[j - stone] + stone)

Correct 1D optimization:

dp = [0] * (target + 1)
for stone in stones:
    for j in range(target, stone - 1, -1):  # Correct! Backward iteration
        dp[j] = max(dp[j], dp[j - stone] + stone)

5. Misunderstanding the Problem Transformation

Not recognizing that the stone smashing process is equivalent to partitioning into two subsets. Some might try to simulate the actual smashing process, which leads to exponential time complexity.

Solution: Understand that after all operations, stones can be divided into two groups where one group's stones are subtracted from the other group's stones. The result is |sum(group1) - sum(group2)|, which we want to minimize.