LeetCode 1049 - Last Stone Weight II

The problem is essentially about simulating the process of repeatedly smashing stones together until at most one stone remains. Each stone has a positive integer weight.

leetcodemediumarraydynamic-programming

LeetCode Problem 1049

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem is essentially about simulating the process of repeatedly smashing stones together until at most one stone remains. Each stone has a positive integer weight. When two stones are chosen, if their weights are equal, both are destroyed; if they are unequal, the smaller stone is destroyed, and the larger stone's weight is reduced by the smaller stone's weight. The goal is not to simulate the process naively, but rather to find the minimum possible weight of the remaining stone after performing any sequence of smash operations optimally.

The input is an array of integers stones where each integer represents the weight of a stone. The output is a single integer representing the smallest possible leftover stone weight. The constraints tell us that the length of the array is at most 30 and each weight is at most 100, meaning brute-force approaches are not practical, but dynamic programming or subset-sum approaches are feasible.

Important edge cases include arrays with a single stone, arrays where all stones have the same weight, and arrays where the sum of all stones is odd or even, because these affect how the "smash" operations can cancel out weights.

Approaches

The brute-force approach would involve recursively trying every possible pair of stones to smash, keeping track of the resulting stone arrays at each step. This guarantees correctness because it simulates all possible sequences, but the time complexity is exponential due to the vast number of permutations and combinations. For n = 30, this is infeasible.

The optimal approach relies on a key insight: smashing stones can be thought of as partitioning the stones into two groups whose sums are as equal as possible. Each "smash" effectively reduces the problem to the absolute difference of two subsets. Therefore, the problem reduces to a variant of the subset sum problem: find a subset of stones with a sum as close as possible to half of the total sum. The remaining stone weight will be the difference between the total sum and twice the sum of this subset.

Dynamic programming can efficiently solve this by maintaining a boolean array dp where dp[s] is True if a subset of stones sums to s. Iteratively, for each stone, we update possible subset sums. The optimal remaining weight is total_sum - 2 * max_possible_subset_sum.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Recursively simulate all stone smashing sequences; exponential and infeasible for n=30
Optimal O(n * total_sum/2) O(total_sum/2) Uses DP subset sum approach; efficient due to constraints

Algorithm Walkthrough

  1. Compute the total sum of all stones. This represents the upper limit of the possible sum of any subset.
  2. Initialize a boolean DP array dp of size (total_sum // 2 + 1) with dp[0] = True. Each index represents a potential subset sum; True means it is achievable.
  3. Iterate through each stone. For each stone, update the DP array in reverse (from high to low) to avoid using a stone multiple times in one iteration. For a stone with weight w, mark dp[s] = True if dp[s - w] is True.
  4. After processing all stones, find the largest s such that dp[s] is True. This s is the sum of one subset closest to half of the total sum.
  5. Compute the minimum possible remaining stone weight as total_sum - 2 * s.

Why it works: The DP array represents all achievable subset sums. By finding the subset sum closest to half of the total sum, we are effectively balancing the stones into two groups with minimal difference, which directly corresponds to the minimum leftover stone weight after all possible smashes.

Python Solution

from typing import List

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total_sum = sum(stones)
        target = total_sum // 2
        dp = [False] * (target + 1)
        dp[0] = True
        
        for weight in stones:
            for s in range(target, weight - 1, -1):
                dp[s] = dp[s] or dp[s - weight]
        
        for s in range(target, -1, -1):
            if dp[s]:
                return total_sum - 2 * s

The implementation first calculates the total sum and the half-sum target. The DP array tracks achievable subset sums. By iterating in reverse order, we prevent double-counting a stone. Finally, we find the largest achievable sum ≤ half of total sum, and compute the minimal leftover weight accordingly.

Go Solution

func lastStoneWeightII(stones []int) int {
    totalSum := 0
    for _, w := range stones {
        totalSum += w
    }
    target := totalSum / 2
    dp := make([]bool, target+1)
    dp[0] = true
    
    for _, weight := range stones {
        for s := target; s >= weight; s-- {
            dp[s] = dp[s] || dp[s-weight]
        }
    }
    
    for s := target; s >= 0; s-- {
        if dp[s] {
            return totalSum - 2*s
        }
    }
    return 0
}

The Go solution mirrors the Python logic. Note the slice initialization, iteration order, and boolean operations. Reverse iteration prevents reuse of a stone within the same iteration.

Worked Examples

Example 1: stones = [2,7,4,1,8,1]

Total sum = 23, target = 11. DP array tracks achievable sums up to 11.

Stone DP Achievable Sums (True indices)
2 0,2
7 0,2,7,9
4 0,2,4,6,7,9,11
1 0,1,2,3,4,5,6,7,8,9,10,11
8 update dp
1 final dp

Minimum remaining weight = 23 - 2*11 = 1.

Example 2: stones = [31,26,33,21,40]

Total sum = 151, target = 75. DP finds max achievable subset sum ≤ 75 = 73.

Minimum remaining weight = 151 - 2*73 = 5.

Complexity Analysis

Measure Complexity Explanation
Time O(n * total_sum/2) Each stone iterates over subset sums up to total_sum/2
Space O(total_sum/2) DP array of size total_sum/2 tracks achievable subset sums

The constraints (n ≤ 30, stones[i] ≤ 100) make this feasible since total_sum/2 ≤ 1500.

Test Cases

# Provided examples
assert Solution().lastStoneWeightII([2,7,4,1,8,1]) == 1  # example 1
assert Solution().lastStoneWeightII([31,26,33,21,40]) == 5  # example 2

# Edge cases
assert Solution().lastStoneWeightII([1]) == 1  # single stone
assert Solution().lastStoneWeightII([1,1]) == 0  # two equal stones
assert Solution().lastStoneWeightII([1,2,3,4,5]) == 1  # odd total sum
assert Solution().lastStoneWeightII([100]*30) == 0  # max weights
Test Why
[2,7,4,1,8,1] Basic example with multiple smashes
[31,26,33,21,40] Larger numbers, subset sum non-trivial
[1] Single element, minimal edge
[1,1] Two equal stones cancel out
[1,2,3,4,5] Total sum odd, leftover must be non-zero
[100]*30 Stress test for upper bounds

Edge Cases

  1. Single stone array: If there is only one stone, no smash can occur. The algorithm correctly returns the weight of the single stone because the DP array initializes dp[0] = True and no other subset sums are added.
  2. All stones equal: For arrays where all stones have the same weight, an even number of stones will cancel out completely. The DP approach correctly finds a subset that sums to half the total sum, resulting in a leftover of 0.
  3. Odd total sum: When the sum of all stones is odd, it is impossible to split perfectly into two equal sums. The DP solution ensures the largest achievable sum ≤ half of total sum is selected, producing the minimal positive leftover. This avoids pitfalls where naive greedy subtraction could fail.

This dynamic programming approach ensures correctness, efficiency, and handles edge cases seamlessly.