The O(n) Club: Last Stone Weight II—Divide, Conquer, (Don’t Smash)

The O(n) Club: Last Stone Weight II—Divide, Conquer, (Don’t Smash)

⚡ TL;DR

Ignore the chaotic demo derby. This problem is really about dividing stones into two groups as close in weight as possible—like splitting a bar tab during a power outage. Use dynamic programming (yes, subset sum). Sample Java wizardry:

// Pretend to smash stones, but actually…
int sum = 0;
for (int s : stones) sum += s;
boolean[] dp = new boolean[sum / 2 + 1];
dp[0] = true;
for (int stone : stones)
    for (int j = dp.length - 1; j >= stone; j--)
        dp[j] |= dp[j - stone];
for (int j = dp.length - 1; ; j--)
    if (dp[j]) {
        System.out.println(sum - 2 * j);
        break;
    }

🧠 How Devs Usually Mess This Up

The rookie move: simulate every single smash, like you’re writing your own fighting game physics engine. Result? Code with the runtime of a slow-motion car crash. The twist: the only thing that matters is splitting up stone weights as evenly as possible. Simulating every smash is like microwaving popcorn by rubbing the kernels together. Please don’t.

🔍 What’s Actually Going On

Think less rock ’em sock ’em and more let’s balance two scales. We’re really trying to split stones into two teams with a weight difference as small as your tolerance for off-by-one errors. Imagine loading two delivery trucks so neither tips over. The wild smashing story in the problem is really just a sneaky rebranding of the partition subset sum—so classic, it should come with bell bottoms.

🛠️ PseudoCode

• Sum all the stones in the array.
  int totalSum = sum(stones);
  The more you have, the bigger the headache.
• Make a DP array up to half the total sum.
  boolean[] dp = new boolean[totalSum / 2 + 1]; dp[0] = true;
  You’re looking for subset sums, not lost change on the floor.
• For each stone, update which sums you can reach.
  for (stone : stones) for (j = dp.length - 1; j >= stone; j--) dp[j] |= dp[j - stone];
  Backwards loop: the universal DP hot tip.
• Find the largest j where dp[j] is true.
  for (j = half; j >= 0; j--)
  Closest you can get to splitting the total weight in half.
• Answer: totalSum – 2 * j
  That’s the stone left standing after all imaginary WWE action.

💻 The Code

public int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for (int s : stones) sum += s;
    int half = sum / 2;
    boolean[] dp = new boolean[half + 1];
    dp[0] = true;
    for (int stone : stones) {
        for (int j = half; j >= stone; j--) {
            dp[j] = dp[j] || dp[j - stone];
        }
    }
    for (int j = half; j >= 0; j--) {
        if (dp[j]) {
            return sum - 2 * j;
        }
    }
    // If this happens, you’ve somehow broken the universe.
    return 0;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Recursive smash simulation? Enter factorial sadness. Stick to DP like sticky notes in a dev’s cubicle.
• Watch the dp size. Big weights can bloat memory faster than a pizza at hackathon midnight.
• Edge cases: All stones the same? Easy split for even count; otherwise, one stubborn stone left.
• Time: O(N * W/2). Space: also O(W/2). Greedy won’t save you, no matter how many stones you throw.

🧠 Interviewer Brain-Tattoo

Don’t get lost in simulated carnage—partition like a pro, and let DP do the heavy lifting (and the heavy smashing).