Last Stone Weight II

MEDIUM✓ CHIP-TIMEDLC #1049 — FULL STATEMENT ↗

The drill: Stones get smashed together two at a time — the heavier one survives, reduced by the lighter one's weight, and equal weights destroy both. Choosing the smashing order freely, find the smallest possible weight the last stone can end up with.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A collection of stone weights arrives, and stones get smashed together two at a time: the heavier stone survives, reduced by the lighter stone's weight, while equal weights destroy each other completely.

Which two stones get smashed together at each step is entirely up to the chooser, and the order can be picked freely to try to leave the smallest possible weight behind at the very end.

The task is to find that smallest achievable final weight — either a single stone's leftover weight, or zero if every stone cancels out completely.

EX 01

stones = [9]

→ 9

SINGLE STONE, NOTHING TO SMASH

EX 02

stones = [5, 9]

→ 4

TWO STONES, ONE COLLISION

EX 03

stones = [6, 6]

→ 0

EQUAL STONES ANNIHILATE COMPLETELY

stone weights are positive integers
arrays run up to a few dozen stones
smashing order can be chosen freely to minimize the result
the final weight is zero when everything cancels out exactly

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

However the smashing plays out, every stone ends up contributing to one of exactly two totals — the two 'sides' that keep colliding into whatever survives. The final weight is just the difference between those two sides.

HINT 2 THE STRUCTURE

So the real question isn't about smashing order at all: split the stones into two groups so their sums land as close together as possible. That's a subset-sum question wearing a costume.

HINT 3 ONE STEP FROM THE ANSWER

Let target = total // 2. Find the largest achievable subset sum ≤ target with a reachability DP over sums 0..target — the answer is total − 2 × that best reachable sum.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE EVEN SPLITPATTERN · SUBSET SUM — REACHABILITY DPstones = [2, 4, 5]

STEP 1

stones=[2,4,5], total=11, target=11//2=5. reachable[0]=true from the start — zero needs no stones at all.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/last-stone-weight-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2
        reachable = [False] * (target + 1)
        reachable[0] = True
        for s in stones:
            for t in range(target, s - 1, -1):
                if reachable[t - s]:
                    reachable[t] = True
        best = next(t for t in range(target, -1, -1) if reachable[t])
        return total - 2 * best

TIME O(N · SUM)SPACE O(SUM)PYTHON · RACE PACE · 12 LN

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        n = len(stones)
        best = total  # everything on one side, nothing on the other
        for mask in range(1 << n):
            side = 0
            for i in range(n):
                if mask & (1 << i):
                    side += stones[i]
            best = min(best, abs(total - 2 * side))
        return best

TIME O(2^N · N)SPACE O(1)PYTHON · TRAINING PACE · 12 LN

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

TIME O(N · SUM)SPACE O(SUM)JAVA · RACE PACE · 26 LN

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int total = 0;
        for (int s : stones) {
            total += s;
        }
        int best = total;
        for (int mask = 0; mask < (1 << n); mask++) {
            int side = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    side += stones[i];
                }
            }
            best = Math.min(best, Math.abs(total - 2 * side));
        }
        return best;
    }
}

TIME O(2^N · N)SPACE O(1)JAVA · TRAINING PACE · 20 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED