The O(n) Club: Coin Change, Dynamic Pain Edition

The O(n) Club: Coin Change, Dynamic Pain Edition

⚡ TL;DR

Unlimited coins, fickle denominations, one goal: fewest coins to make your amount. Don’t be greedy—be dynamic! Here’s a brute, slow first try:

// Brute force, a.k.a. "CPU heater"
int minCoins(int[] coins, int amount) {
    if (amount == 0) return 0;
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        if (amount - coin >= 0) {
            int res = minCoins(coins, amount - coin);
            if (res != -1) min = Math.min(min, res + 1);
        }
    }
    return min == Integer.MAX_VALUE ? -1 : min;
}

🧠 How Devs Usually Mess This Up

Dev instinct #1: Grab the biggest coins possible. Problem solved—except when it isn’t. With coins [1, 3, 4] and amount 6, greedy says (4,1,1). Optimal says (3,3). Sorry, you don’t always get the shiny nickel.

Dev instinct #2: Forgetting coin supply is infinite—it’s not a birthday grab bag, you can take the same coin again and again.

Dev instinct #3: Ignoring when the answer doesn’t exist. (No, Java won’t pay you in exposure, and you shouldn’t return 99999 coins.)

🔍 What’s Actually Going On

Picture building a tower with Legos: unlimited blocks of various sizes. You want exact height with minimal blocks. The secret? Don’t just start stacking the biggest block—sometimes lots of medium blocks do better. So you brute force every combo? Not unless you moonlight as a CPU miner. Enter dynamic programming: save answers for small towers, reuse them for the bigger ones. Build up from zero, no repeats, less tears.

🛠️ PseudoCode

• Set up dp[amount + 1], all slots = infinity (a.k.a. amount+1), except dp[0]=0 (’cause zero coins make zero).
• For amount = 1 to amount:
  • For each coin:
    • If you can use it (amount - coin >= 0): dp[amount] = min(dp[amount], dp[amount - coin] + 1)
• If dp[amount] is still infinity, return -1. Else, return dp[amount].

💻 The Code

// Bottom-up, slick and quick
int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[max];
    Arrays.fill(dp, max); // Assume worst-case
    dp[0] = 0; // No coins for zero amount
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i - coin >= 0)
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == max ? -1 : dp[amount];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t forget amount=0 (return 0, unless you believe in negative coins).
• Impossible combos? Return -1 like a civilized person.
• Time: O(amount × coins). Space: O(amount). Less than the number of Slack channels you have open.
• Greedy fails unless your denominations are magic (canonical), so don’t fall for it.

🧠 Interviewer Brain-Tattoo

“Coin Change: If you reach for greed, you’ll make cents, not sense. Dynamic programming is the currency real devs use.”