Coin Change I

Link: https://leetcode.com/problems/coin-change/

Problem Statement

Given an integer array coins representing coins of different denominations and an integer amount, return the fewest number of coins that you need to make up that amount. If that amount cannot be made up, return -1.

Intuition

At each step, we can either:

Pick the coin (and stay at the same index because we can use it unlimited times), or
Not pick and move to the next coin.

We explore all valid paths and choose the one requiring the minimum number of coins.

1. Recursion (Top-Down)

IBH Format

Induction: minCoins(index, target)
Base Case:
- If index == 0:
  - If target % coins[0] == 0, return target / coins[0]
  - Else return ∞ (i.e., Integer.MAX_VALUE)
Hypothesis: Recursively call for pick and not-pick
Induction Step: Take the min of pick and not-pick

Java Code

class Solution {
    public int coinChange(int[] coins, int amount) {
        int ans = helper(coins.length - 1, amount, coins);
        return (ans >= (int)1e9) ? -1 : ans;
    }

    private int helper(int i, int amount, int[] coins) {
        if (i == 0) {
            if (amount % coins[0] == 0) return amount / coins[0];
            else return (int)1e9;
        }

        int notPick = helper(i - 1, amount, coins);
        int pick = Integer.MAX_VALUE;
        if (coins[i] <= amount)
            pick = 1 + helper(i, amount - coins[i], coins);

        return Math.min(pick, notPick);
    }
}

Time Complexity

O(2^n) (Exponential, worst case)

2. Memoization (Top-Down with Caching)

Java Code

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        int ans = helper(n - 1, amount, coins, dp);
        return (ans >= (int)1e9) ? -1 : ans;
    }

    private int helper(int i, int amount, int[] coins, int[][] dp) {
        if (i == 0) {
            if (amount % coins[0] == 0) return amount / coins[0];
            else return (int)1e9;
        }

        if (dp[i][amount] != -1) return dp[i][amount];

        int notPick = helper(i - 1, amount, coins, dp);
        int pick = Integer.MAX_VALUE;
        if (coins[i] <= amount)
            pick = 1 + helper(i, amount - coins[i], coins, dp);

        return dp[i][amount] = Math.min(pick, notPick);
    }
}

Time and Space Complexity

Time: O(n * amount)
Space: O(n * amount) + O(n) (for recursion stack)

3. Tabulation (Bottom-Up)

Java Code

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];

        for (int t = 0; t <= amount; t++) {
            if (t % coins[0] == 0) dp[0][t] = t / coins[0];
            else dp[0][t] = (int)1e9;
        }

        for (int i = 1; i < n; i++) {
            for (int t = 0; t <= amount; t++) {
                int notPick = dp[i - 1][t];
                int pick = (coins[i] <= t) ? 1 + dp[i][t - coins[i]] : (int)1e9;
                dp[i][t] = Math.min(pick, notPick);
            }
        }

        return dp[n - 1][amount] >= (int)1e9 ? -1 : dp[n - 1][amount];
    }
}

Time and Space Complexity

Time: O(n * amount)
Space: O(n * amount)

4. Space Optimization

Use two 1D arrays instead of a 2D table.

Java Code

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] prev = new int[amount + 1];

        for (int t = 0; t <= amount; t++) {
            if (t % coins[0] == 0) prev[t] = t / coins[0];
            else prev[t] = (int)1e9;
        }

        for (int i = 1; i < n; i++) {
            int[] curr = new int[amount + 1];
            for (int t = 0; t <= amount; t++) {
                int notPick = prev[t];
                int pick = (coins[i] <= t) ? 1 + curr[t - coins[i]] : (int)1e9;
                curr[t] = Math.min(pick, notPick);
            }
            prev = curr;
        }

        return prev[amount] >= (int)1e9 ? -1 : prev[amount];
    }
}

Time and Space Complexity

Time: O(n * amount)
Space: O(2 * amount) → optimized to O(amount)

Choice Diagram

                   helper(i, t)
                  /            \
        Not Pick                  Pick
    helper(i-1, t)       1 + helper(i, t - coins[i])

Conclusion

The Coin Change problem is a classic unbounded knapsack variation. The recursion-based solution provides clarity, memoization adds efficiency, and space optimization makes the solution scalable for large inputs.