Scale Engineer

Last Stone Weight II

Med
#1002Time: O(2^n), where `n` is the number of stones. For each stone, we make two recursive calls, leading to an exponential number of computations.Space: O(n), where `n` is the number of stones. This space is used by the recursion call stack.
Patterns
Dynamic Programming
Data structures
Array

Prompt

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

We are playing a game with the stones. On each turn, we choose any two stones 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 destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

 

Example 1:

Input: stones = [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.

Example 2:

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

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores every possible way to partition the stones into two groups. For each stone, we can either place it in the first group or the second. This creates 2^n possible partitions, where n is the number of stones. We can implement this using a recursive function that tries both possibilities for each stone and finds the minimum possible difference between the two groups' sums.

Algorithm

  1. The core idea is to simulate the smashing process by partitioning the stones into two groups. The final weight is the absolute difference between the total weights of these two groups.
  2. We define a recursive function, for example, findMinWeight(index, sum1, sum2).
  3. index: The index of the current stone being considered.
  4. sum1, sum2: The current total weights of the two groups.
  5. Base Case: When index reaches the end of the stones array, all stones have been assigned to a group. We return the absolute difference abs(sum1 - sum2).
  6. Recursive Step: For the stone at stones[index], we explore two possibilities:
    • Add stones[index] to the first group: Make a recursive call findMinWeight(index + 1, sum1 + stones[index], sum2).
    • Add stones[index] to the second group: Make a recursive call findMinWeight(index + 1, sum1, sum2 + stones[index]).
  7. The function returns the minimum of the results from these two recursive calls.
  8. The initial call to start the process is findMinWeight(0, 0, 0).

Walkthrough

The problem of finding the minimum last stone weight can be rephrased as partitioning the set of stones into two subsets, S1 and S2, such that the absolute difference of their sums, |sum(S1) - sum(S2)|, is minimized. This is because smashing two stones x and y to get y - x is equivalent to putting them in different groups. The brute-force approach systematically explores all 2^n possible partitions. A recursive function can be designed to handle this exploration. For each stone, the function makes two recursive calls: one where the stone is added to S1 and another where it's added to S2. The base case for the recursion is when all stones have been assigned, at which point we compute the difference and compare it with the minimum difference found so far.

class Solution {    public int lastStoneWeightII(int[] stones) {        return findMinWeight(stones, 0, 0, 0);    }     private int findMinWeight(int[] stones, int index, int sum1, int sum2) {        if (index == stones.length) {            return Math.abs(sum1 - sum2);        }         // Option 1: Add the current stone to the first group        int diff1 = findMinWeight(stones, index + 1, sum1 + stones[index], sum2);         // Option 2: Add the current stone to the second group        int diff2 = findMinWeight(stones, index + 1, sum1, sum2 + stones[index]);         return Math.min(diff1, diff2);    }}

Complexity

Time

O(2^n), where `n` is the number of stones. For each stone, we make two recursive calls, leading to an exponential number of computations.

Space

O(n), where `n` is the number of stones. This space is used by the recursion call stack.

Trade-offs

Pros

  • Conceptually simple and straightforward to implement.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

class Solution {public  int lastStoneWeightII(int[] stones) {    int s = 0;    for (int v : stones) {      s += v;    }    int m = stones.length;    int n = s >> 1;    int[] dp = new int[n + 1];    for (int v : stones) {      for (int j = n; j >= v; --j) {        dp[j] = Math.max(dp[j], dp[j - v] + v);      }    }    return s - dp[n] * 2;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem