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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 201 <= stones[i] <= 100
Hints for Last Stone Weight II
Hint 1
Every smash assigns a stone a sign: the final weight is
|sum of one group - sum of the other|.Hint 2
So the task is to split the stones into two groups whose sums are as close as possible.
Hint 3
That is subset-sum: find the largest reachable sum at most
total / 2, and the answer istotal - 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
- Set
half = total // 2anddp[0] = true. - For each stone, for
wfromhalfdown tostone,dp[w] |= dp[w - stone]. - Return
total - 2·wfor the largest reachablew.
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 totalJava
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