Skip to main content

1049. Last Stone Weight II

medium

Smash stones into two groups; minimize the final residue. Reduces to: pick a subset closest to half the total — knapsack feasibility maximized.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Constraints

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

Examples

Example 1

Input
stones = [2,7,4,1,8,1]
Output
1

Explanation: We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then, combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then, combine 2 and 1 to get 1, so the array converts to [1,1,1] then, combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2

Input
stones = [31,26,33,21,40]
Output
5

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Equivalent: assign each stone a + or - so the resulting absolute sum is minimal.

Hint 2

If P is the sum of the + group and N of the - group, total = P + N and answer = |P - N| = total - 2P.

Hint 3

Minimize that by maximizing P with P <= total/2. Subset-sum knapsack on the array.

Solution approach

Reveal approach

Any sequence of smashes corresponds to assigning each stone a + or - sign and the final residue equals |sum(+) - sum(-)|. To minimize the residue, minimize total - 2*P where P is the subset sum of the + group, constrained to P <= total/2. Solve via boolean knapsack: dp[s] is whether some subset sums to s, for s up to total/2. Initialize dp[0] = true. For each stone w, sweep s from total/2 down to w and set dp[s] |= dp[s - w]. Scan dp from total/2 downward to find the largest reachable P. Return total - 2*P. O(n * total) time, O(total) space.

Complexity

Time
O(n * sum)
Space
O(sum)

Related patterns

  • dynamic-programming
  • knapsack-0-1

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Last Stone Weight II and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →