Last Stone Weight II

Last Stone Weight II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (0/1 Knapsack Subset Sum Style) subpattern.

Problem statement

You are given a collection of stones in stones, where each integer represents one stone's weight. In one operation, choose any two remaining stones and smash them together. If their weights are equal, both disappear; otherwise, the lighter stone disappears and the heavier stone is replaced by a stone whose weight is the difference between the two.

Continue until at most one stone remains. Choose the operations so that the weight of the final stone is as small as possible. Return that minimum possible weight as an integer. If no stone remains, return 0.

Example 1:

Input: stones = [2,3,7] Output: 2 Explanation: The stones can be divided into groups with weights 7 and 5, so repeated smashing can leave a stone weighing 2. No arrangement produces a smaller difference.

Example 2:

Input: stones = [1,1,1,1,1] Output: 1 Explanation: Three stones can be balanced against two stones, giving group weights 3 and 2 and a final difference of 1.

Example 3:

Input: stones = [4,9,3,8] Output: 0 Explanation: The stones can be split into groups of equal total weight: 4 + 8 and 9 + 3. Smashing within and between the groups can eliminate every stone.

Constraints:

- 1 <= stones.length <= 30 - 1 <= stones[i] <= 1000 - stones contains only integers - The input is provided as a JSON array under the key stones

Topics and companies

Topics: Array, Dynamic Programming, Counting.

How to practise Last Stone Weight II on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * S), where n is the number of stones and S is the total stone weight. time and O(S) space.

Open Last Stone Weight II in the code editor, or read the Last Stone Weight II editorial for a worked solution with its approach and complexity analysis.

Where Last Stone Weight II sits in the DSA pattern sheet

Problems related to Last Stone Weight II

Other problems that use the same 1D Array (0/1 Knapsack Subset Sum Style) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.