Last Stone Weight II

Medium
328.

Last Stone Weight II

Last Stone Weight II is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

Repeatedly smash any two stones together. If they weigh x and y with x <= y, the stone of weight x is destroyed and the other becomes y - x; equal stones destroy each other. Return the smallest possible weight of the stone left at the end, or 0 if none remains.

Example 1

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

Example 2

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

Example 3

Input
stones = [1,1]
Output
0

Constraints

  • 1 <= stones.length <= 20
  • 1 <= stones[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function(stones) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Last Stone Weight II — Solution in Python, Java & C++

Last Stone Weight II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Last Stone Weight II is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

Repeatedly smash any two stones together. If they weigh x and y with x <= y, the stone of weight x is destroyed and the other becomes y - x; equal stones destroy each other. Return the smallest possible weight of the stone left at the end, or 0 if none remains.

Example 1

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

Example 2

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

Example 3

Input: stones = [1,1]
Output: 0

Constraints

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

Hints for Last Stone Weight II

  1. Hint 1

    Every smash assigns a stone a sign: the final weight is |sum of one group - sum of the other|.

  2. Hint 2

    So the task is to split the stones into two groups whose sums are as close as possible.

  3. Hint 3

    That is subset-sum: find the largest reachable sum at most total / 2, and the answer is total - 2 × that.

How to solve Last Stone Weight II

Each smash assigns the stones signs, so the final weight is |S₁ - S₂| for a partition of the stones. Find the largest reachable subset sum at most total / 2 with a boolean knapsack.

Approach

  1. Set half = total // 2 and dp[0] = true.
  2. For each stone, for w from half down to stone, dp[w] |= dp[w - stone].
  3. Return total - 2·w for the largest reachable w.

Why it works

Any sequence of smashes yields a signed sum of the weights, and any signed sum with both signs present is achievable, so minimising the final stone is minimising |total - 2·S| over subset sums S.

Complexity

  • Time — O(n · total)
  • Space — O(total)

Pitfalls

  • Iterate the weight downward so each stone is used at most once.

Reference solution

Python

def lastStoneWeightII(stones) -> int:
    total = sum(stones)
    half = total // 2
    dp = [False] * (half + 1)
    dp[0] = True
    for stone in stones:
        for w in range(half, stone - 1, -1):
            if dp[w - stone]:
                dp[w] = True
    for w in range(half, -1, -1):
        if dp[w]:
            return total - 2 * w
    return total

Java

public static int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int s : stones) total += s;
    int half = total / 2;
    boolean[] dp = new boolean[half + 1];
    dp[0] = true;
    for (int s : stones) {
        for (int w = half; w >= s; w--) {
            if (dp[w - s]) dp[w] = true;
        }
    }
    for (int w = half; w >= 0; w--) {
        if (dp[w]) return total - 2 * w;
    }
    return total;
}

C++

int lastStoneWeightII(vector<int>& stones) {
    int total = 0;
    for (int s : stones) total += s;
    int half = total / 2;
    vector<char> dp(half + 1, 0);
    dp[0] = 1;
    for (int s : stones) {
        for (int w = half; w >= s; w--) {
            if (dp[w - s]) dp[w] = 1;
        }
    }
    for (int w = half; w >= 0; w--) {
        if (dp[w]) return total - 2 * w;
    }
    return total;
}

JavaScript

var lastStoneWeightII = function(stones) {
    let total = 0;
    for (let i = 0; i < stones.length; i++) total += stones[i];
    const half = Math.floor(total / 2);
    const dp = new Array(half + 1).fill(false);
    dp[0] = true;
    for (let i = 0; i < stones.length; i++) {
        for (let w = half; w >= stones[i]; w--) {
            if (dp[w - stones[i]]) dp[w] = true;
        }
    }
    for (let w = half; w >= 0; w--) {
        if (dp[w]) return total - 2 * w;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming