Command Palette

Search for a command to run...

Hectal
Problem 30.3 · Knapsack DPMedium

Last Stone Weight II

PatternKnapsack DP

What it teaches: Recognising a hidden partition: the result is the difference between two groups.

Practise it on judges as “Last Stone Weight II”.

The problem

Smash any two stones: equal ones vanish, otherwise the difference remains. Return the smallest possible weight of the last stone (0 if none).

Example 1

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

Constraints

  • 1 ≤ n ≤ 30
  • 1 ≤ stone ≤ 100

Pattern clues in the wording

  • → Any order of pairwise differences

These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int lastStoneWeightII(int[] stones) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
stones = [2,7,4,1,8,1]
1
2
stones = [31,26,33,21,40]
5

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Boolean knapsack to half · O(n × total)
1

Boolean knapsack to half

Time O(n × total) Space O(total)

Reachable sums up to total / 2; the largest reachable s gives total − 2s.

Approach 1
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int s : stones) total += s;
        int half = total / 2;
        boolean[] can = new boolean[half + 1];
        can[0] = true;
        for (int s : stones)
            for (int c = half; c >= s; c--) can[c] |= can[c - s];
        for (int c = half; ; c--) if (can[c]) return total - 2 * c;
    }
}

Verdict: Same code as equal partition.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One stone
  • Perfect split (0)

Mistakes people make

  • Simulating with a heap (that's Last Stone Weight I, a different rule).

Interview

Follow-up questions

Why can every split be achieved by some smashing order?