Coin Change Problem

Problem Statement

Given an array of coin denominations and a total amount, find the minimum number of coins needed to make up that amount. If it's not possible, return -1.

Example:

• Input: coins = [1, 5, 10, 25], amount = 30
• Output: 2 (one 5-cent coin + one 25-cent coin)

Noob-Friendly Explanation

Imagine you're at a candy store and the candy costs 30 rupees. You have unlimited coins of ₹1, ₹5, ₹10, and ₹25. You want to pay using as few coins as possible. You wouldn't pay with 30 one-rupee coins, right? You'd pick a ₹25 coin and a ₹5 coin — just 2 coins! That's exactly what this problem asks: find the fewest coins to make the exact total.

Approach 1: Brute Force (Recursion)

Intuition

Try every possible combination of coins. For each coin, you either use it (and reduce the amount) or skip it. Pick the combination that uses the fewest coins.

Algorithm

1. If the amount is 0, return 0 (no coins needed)
2. If the amount is negative, return -1 (not possible)
3. For each coin, recursively try using it and find the minimum

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        int minCoins = Integer.MAX_VALUE;

        for (int coin : coins) {
            int result = coinChange(coins, amount - coin);
            if (result != -1) {
                minCoins = Math.min(minCoins, result + 1);
            }
        }

        return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - In the worst case we explore all combinations
• Space Complexity: O(n) - Recursion stack depth can go up to the amount

Approach 2: Optimal (Bottom-Up DP)

Intuition

Instead of recalculating the same sub-problems again and again, we build a table. dp[i] stores the minimum coins needed to make amount i. We fill it from 0 up to the target amount.

Algorithm

1. Create a dp array of size amount + 1, filled with amount + 1 (an impossible large value)
2. Set dp[0] = 0 (0 coins needed for amount 0)
3. For each amount from 1 to target, try every coin. If the coin fits, update dp[i] = min(dp[i], dp[i - coin] + 1)
4. If dp[amount] is still the impossible value, return -1

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // Fill with a value larger than any possible answer
        java.util.Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Complexity Analysis

• Time Complexity: O(n * amount) - Two nested loops: one over amounts, one over coins
• Space Complexity: O(amount) - We use a single 1D array of size amount + 1