Coin Change

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

You have unlimited copies of each denomination in coins. Build exactly amount using the fewest coins.

Examples

Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1
No combination of 2s can produce 3.

Example 3:
Input: coins = [1], amount = 0
Output: 0
Zero amount needs zero coins.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

🎯 Real-World Analogy

Building a Target Budget with Coupon Packs

Imagine you need to hit an exact budget total and you can buy coupon packs worth fixed values: 1, 2, 5, etc. You can buy each pack type as many times as needed.

For each target value from 1 to amount, ask: "If I end with coin c, what was the best answer for target - c?" Then add one coin.

Dynamic programming works because every larger target is built from smaller targets we already solved.

💡 Key Insights

State definition: dp[x] = minimum coins to form amount x.
Transition: dp[x] = min(dp[x], dp[x - coin] + 1) for valid coins.
Base case: dp[0] = 0 (zero amount takes zero coins).
Use sentinel amount + 1 to represent "unreachable".
Answer is -1 if dp[amount] stayed unreachable.

💻 Solution Approaches

Approach 1: DFS + Memoization

Time: O(N * amount) | Space: O(amount)

Recursive search with memoization over remaining amount. Cleaner recurrence, but recursion depth can be a concern in some languages.

Approach 2: Bottom-Up DP (Recommended)

Time: O(N * amount) | Space: O(amount)

Iteratively compute the minimum coins for every amount from 1 to target. This is predictable and interview-friendly.

Python Implementation

          from typing import List


def coin_change(coins: List[int], amount: int) -> int:
    """
    Bottom-up dynamic programming.

    dp[x] = minimum coins needed to form amount x.

    Time: O(len(coins) * amount)
    Space: O(amount)
    """
    if amount == 0:
        return 0

    # Sentinel larger than any possible optimal coin count.
    unreachable = amount + 1
    dp = [unreachable] * (amount + 1)
    dp[0] = 0

    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current:
                candidate = dp[current - coin] + 1
                if candidate < dp[current]:
                    dp[current] = candidate

    return -1 if dp[amount] == unreachable else dp[amount]
        

JavaScript Implementation

          function coinChange(coins, amount) {
  /**
   * Bottom-up dynamic programming.
   *
   * Time: O(coins.length * amount)
   * Space: O(amount)
   */
  if (amount === 0) return 0;

  const unreachable = amount + 1;
  const dp = new Array(amount + 1).fill(unreachable);
  dp[0] = 0;

  for (let current = 1; current <= amount; current++) {
    for (const coin of coins) {
      if (coin <= current) {
        const candidate = dp[current - coin] + 1;
        if (candidate < dp[current]) {
          dp[current] = candidate;
        }
      }
    }
  }

  return dp[amount] === unreachable ? -1 : dp[amount];
}
        

🔍 Step-by-Step Walkthrough

Trace coins = [1,2,5], amount = 11:

Initialize:
          dp[0] = 0, all others = 12 (unreachable)

            Amount 1: min(dp[0]+1) = 1 -> dp[1] = 1
          
            Amount 2: min(dp[1]+1, dp[0]+1) = 1 -> dp[2] = 1
          
            Amount 5: coin 5 gives dp[0]+1 = 1 -> dp[5] = 1
          
            Amount 10: two 5-coins -> dp[10] = 2
          
            Amount 11: best is dp[10] + 1 = 3 -> Answer = 3

⚡ Complexity Analysis

Time Complexity: O(N * amount)

Outer loop: one pass for each target value from 1 to amount.
Inner loop: try every coin for each target value.
Total: amount * len(coins) updates.

Space Complexity: O(amount)

DP array: stores best answer for each value 0..amount.
No 2D table: only one dimension is needed.

🔧 Edge Cases

amount = 0 -> return 0
No solution exists (example: coins=[2], amount=3) -> return -1
Single coin denomination repeated many times
Large amount with many denominations (performance still bounded by O(N*amount))
Coins are unsorted; algorithm should not depend on sorted input

🧪 Test Cases

Python

          def test_coin_change():
    assert coin_change([1, 2, 5], 11) == 3
    assert coin_change([2], 3) == -1
    assert coin_change([1], 0) == 0
    assert coin_change([1], 2) == 2
    assert coin_change([2, 5, 10, 1], 27) == 4  # 10 + 10 + 5 + 2

    print("✅ all tests passed")
        

JavaScript

          function testCoinChange() {
  console.assert(coinChange([1, 2, 5], 11) === 3, "test 1");
  console.assert(coinChange([2], 3) === -1, "test 2");
  console.assert(coinChange([1], 0) === 0, "test 3");
  console.assert(coinChange([1], 2) === 2, "test 4");
  console.assert(coinChange([2, 5, 10, 1], 27) === 4, "test 5");

  console.log("✅ all tests passed");
}
        

💼 Interview Tips

State the recurrence before writing code: dp[x] = min(dp[x-coin] + 1).
Call out why greedy fails for this problem (not canonical coin systems).
Define and justify your unreachable sentinel.
Explain why this is unbounded knapsack (reuse of same coin allowed).
Mention common extensions: counting combinations and coin reconstruction.

🎓 Key Takeaways

Coin Change is a state-transition DP over amounts, not coins.
Use a sentinel and convert unreachable states back to -1 at the end.
The recurrence is simple; correctness comes from base case and transition order.

← Back to All Algorithms