Last Stone Weight II

MEDIUM

Description

You are given an array of integers stones where stones[i] is the weight of the i^th 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

Checkout 3 different approaches to solve Last Stone Weight II. Click on different approaches to view the approach and algorithm in detail.

Brute-force Recursion

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

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.
We define a recursive function, for example, findMinWeight(index, sum1, sum2).
index: The index of the current stone being considered.
sum1, sum2: The current total weights of the two groups.
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).
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]).
The function returns the minimum of the results from these two recursive calls.
The initial call to start the process is findMinWeight(0, 0, 0).

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 Analysis

Time Complexity: 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 Complexity: O(n), where `n` is the number of stones. This space is used by the recursion call stack.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Last Stone Weight II. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Last Stone Weight II

Patterns:

Dynamic Programming

Data Structures:

Array