Last Stone Weight II: A Leetcode Problem

Jose Iciano

4 min readAug 27, 2020

Problem Link:

https://leetcode.com/problems/last-stone-weight-ii/

Prerequisites:

This article (and problem) assumes you are familiar with the following concepts:

Dynamic Programming
0–1 Knapsack

If not, here are some useful resources:

Problem Statement:

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks 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 totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

Example:

Before I begin explaining, let us look at the example given on Leetcode.

Input: [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,
we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.

Important Information:

To solve this problem, let’s first write out what we know.

The difference between x and y is always positive (how can a stone have negative weight?). So this means y ≥ x.
When x != y , we originally have Stones = [x, y, a, b, c] We remove x and y from Stones, and add in z = y — x. Stones now = [z, a, b, c] . Repeating this, we eventually get a final set, Stones’ = [Z] , where Z is final stone produced.

Out of the original set, we want to perform this operation in a way that gets us the most optimal Z. We can find the best Z by doing the above operation for every possible combination of stones, but that would take too long O(2^n).

A Better Way:

Let us go more in-depth on what was just explained. In the following example, assume that for each pair (x, y), y ≥ x.

Stones = [x, y, a, b, c]. Remove (x, y). Put in z = y - xStones = [z, a, b, c]. Remove (a, b). Put in d = b - aStones = [z, d, c]. Remove (d, c). Put in e = c - dStones = [z, e]. Remove (z, e) Put in add in Z = e - zStones = [Z].

Now, let us more explicitly define Z by tracing through the operations done.

Z = (z) - (e)  = (z) - (d - c)  = (z) - ((a - b) - c)  = (x - y) - ((a - b) - c)  = (x - y) -(a - b) + c  = x - y - a + b + c  = (x + b + c) - (y + a + c)
  
  = X - Y
     X = (x + b + c)
     Y = (y + a + c)

This shows us two formulas we can use.

S = X + Y

This formula just tells us that we can create two sets from Stones and the addition of their weights give us the total weight sum, S.

X - Y = D

This formula show us what we are trying to find. By creating two sets, we want their difference between them to be minimal.

And with some substitutions we can simplify and combine our formulas.

X - Y = D
X = D + YS = X + Y
S = D + Y + Y
S = D + 2Y
S - D = 2Y
(S - D) / 2 = Y

D at its most minimal is 0 (when X = Y). Let us plug in 0 for D.

S / 2 = Y

Minimizing D means maximizing Y so that it is as close to S/2 as possible.

Is this starting to sound familiar? We have an empty bag of elements with a max weight, and we want to maximize the bag’s value.

It’s sounding a lot of like 0-1 Knapsack, right?

That’s right. This problem is actually 0-1 Knapsack in disguise. We can let the sum of stone weights be our bag weight, and the stones be our values.

Algorithm and Code:

Given an array of stones of length n, we can create an (n x S) 2d array, dp.

Run through each item, i, from 1 to n-1. Run through each weight, j, from 1 to S/2.

For each cell, dp[i][j], we ask “what is the maximum Y I can have if I have at most weight j and I can only use stones up to i?”.

At the end, dp[n][s / 2] should hold the answer to our initial problem, “What is the maximum Y I can have with at most weight S/2?”.

Here is a Java implementation of what was described:

Conclusion:

I hope the article was helpful in showing how one should approach a problem that seems confusing initially. It is important to think of all information given and how to use it to reduce the problem to one that you already know.

I also hope it provided a useful exercise and addition for your dynamic programming toolkit.