Last Stone Weight II

NeetCode: Last Stone Weight II · LeetCode: 1049. Last Stone Weight II · Difficulty: Medium

You are given an int[] stones. Each turn pick any two stones with weights x <= y and smash them: if x == y both are destroyed, otherwise the result is one stone of weight y - x. At the end at most one stone is left. Return the smallest possible weight of that stone (0 if none is left).

Example

Text

Input:  stones = [2, 7, 4, 1, 8, 1]    Output: 1
Input:  stones = [31, 26, 33, 21, 40]  Output: 5

Brute force: try every sign assignment

Key insight: whatever the smashing order, the final stone equals |±s1 ± s2 ± ... ± sn|: every stone ends up either added or subtracted. The stones split into two groups with sums A and B, and the goal is to minimise |A - B|. With total = A + B this is total - 2 * min(A, B), so the goal is a subset whose sum is as close to total / 2 as possible from below.

The plain recursion decides, for each stone, whether it joins the first group. It has two branches per stone and no sharing, so it explores 2^n subsets.

Java

class Solution {
    private int go(int[] stones, int i, int sum, int total) {
        if (i == stones.length) {
            return Math.abs(total - 2 * sum);
        }
        int take = go(stones, i + 1, sum + stones[i], total);
        int skip = go(stones, i + 1, sum, total);
        return Math.min(take, skip);
    }

    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int w : stones) {
            total += w;
        }
        return go(stones, 0, 0, total);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lastStoneWeightII(new int[] {2, 7, 4, 1, 8, 1}));
        System.out.println(sol.lastStoneWeightII(new int[] {31, 26, 33, 21, 40}));
        System.out.println(sol.lastStoneWeightII(new int[] {5}));
        System.out.println(sol.lastStoneWeightII(new int[] {}));
    }
}

Output

Time: O(2^n). Space: O(n) recursion depth.

Better: subset-sum table

The recursion revisits the same (i, sum) pairs. There are only n * (total/2 + 1) different ones, so tabulate them: can[i][s] is true if some subset of the first i stones sums to exactly s. Either stone i - 1 is left out (can[i-1][s]) or taken (can[i-1][s - w] when s >= w). Only sums up to total / 2 are needed, because the smaller group never exceeds it. The answer is total - 2 * s for the largest reachable s.

Java

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int w : stones) {
            total += w;
        }
        int half = total / 2;
        int n = stones.length;
        boolean[][] can = new boolean[n + 1][half + 1];
        can[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int w = stones[i - 1];
            for (int s = 0; s <= half; s++) {
                can[i][s] = can[i - 1][s] || (s >= w && can[i - 1][s - w]);
            }
        }
        int best = 0;
        for (int s = half; s >= 0; s--) {
            if (can[n][s]) {
                best = s;
                break;
            }
        }
        return total - 2 * best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lastStoneWeightII(new int[] {2, 7, 4, 1, 8, 1}));
        System.out.println(sol.lastStoneWeightII(new int[] {31, 26, 33, 21, 40}));
        System.out.println(sol.lastStoneWeightII(new int[] {5}));
        System.out.println(sol.lastStoneWeightII(new int[] {}));
    }
}

Output

Time: O(n * total). Space: O(n * total).

Optimal: one boolean row

Row i only reads row i - 1, and only at the same or a smaller sum. So a single row can[s] is enough if each stone updates it from the largest sum down to its weight: going downwards guarantees can[s - w] still holds the value from before this stone, so each stone is used at most once. Time is unchanged, memory drops to O(total). This is pseudo-polynomial: the running time depends on the stone values, not only on their count.

Java

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int w : stones) {
            total += w;
        }
        int half = total / 2;
        boolean[] can = new boolean[half + 1];
        can[0] = true;
        for (int w : stones) {
            for (int s = half; s >= w; s--) {
                if (can[s - w]) {
                    can[s] = true;
                }
            }
        }
        int best = 0;
        for (int s = half; s >= 0; s--) {
            if (can[s]) {
                best = s;
                break;
            }
        }
        return total - 2 * best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lastStoneWeightII(new int[] {2, 7, 4, 1, 8, 1}));
        System.out.println(sol.lastStoneWeightII(new int[] {31, 26, 33, 21, 40}));
        System.out.println(sol.lastStoneWeightII(new int[] {5}));
        System.out.println(sol.lastStoneWeightII(new int[] {}));
    }
}

Output

Time: O(n * total). Space: O(total).

The loop for (int s = half; s >= w; s--) does not run when a stone is heavier than half, so s - w is never negative. The sums are int values, which wrap silently on overflow, so much larger weights would need long.