How do you solve Last Stone Weight II on LeetCode?

Last Stone Weight II (LeetCode #1049) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * target) time complexity and O(target) space complexity. Key insight: The problem can be viewed as a partition problem where we aim to minimize the difference between two groups of stones.

What is the brute force solution for Last Stone Weight II?

The brute force approach for Last Stone Weight II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves simulating every possible combination of stone collisions. We can recursively try smashing every pair of stones and track the resulting weights until we are left with one or no stones. The optimal Optimal Solution approach improves this to O(n * target).

What algorithm or data structure is used to solve Last Stone Weight II?

Last Stone Weight II uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Subset Sum Problem.

What are the interview tips for Last Stone Weight II?

Always think about how to break down the problem into smaller subproblems. Consider edge cases, such as when all stones are the same or when there is only one stone. Explain your thought process clearly to the interviewer, especially when transitioning from brute force to an optimized solution.

What are common mistakes when solving Last Stone Weight II?

Not considering the total weight and how it relates to the possible sums. Failing to use dynamic programming effectively, leading to unnecessary computations.

#1049

Last Stone Weight II

Medium

ArrayDynamic ProgrammingDynamic ProgrammingSubset Sum Problem

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n * target)
Space	O(1)	O(target)

💡

Intuition

Time O(n * target)Space O(target)

Instead of simulating every possible combination, we can think of the problem as partitioning the stones into two groups such that the difference between their weights is minimized. This can be solved using dynamic programming, similar to the subset sum problem.

⚙️

Algorithm

4 steps

1Step 1: Calculate the total weight of all stones.
2Step 2: Use dynamic programming to find all possible sums that can be formed with the stones.
3Step 3: Find the maximum sum that is less than or equal to half of the total weight.
4Step 4: The result will be the total weight minus twice this maximum sum.

solution.py8 lines

1def lastStoneWeightII(stones):
2    total = sum(stones)
3    target = total // 2
4    dp = [0] * (target + 1)
5    for stone in stones:
6        for j in range(target, stone - 1, -1):
7            dp[j] = max(dp[j], dp[j - stone] + stone)
8    return total - 2 * dp[target]

ℹ

Complexity note: The time complexity is O(n * target) where n is the number of stones and target is half the total weight. The space complexity is O(target) because we are using a DP array of size target.

1The problem can be viewed as a partition problem where we aim to minimize the difference between two groups of stones.
2Dynamic programming helps us efficiently explore possible sums instead of brute-forcing through all combinations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.