Coin Change

Problem

You are given an integer array coins representing coin denominations, and an integer amount. Return the fewest number of coins needed to make up that amount. If it can't be made, return -1. You may assume each denomination has an infinite supply.

Example: coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1).

What the interviewer is testing

• Do you correctly identify that greedy fails (unlike US coins, arbitrary denominations require DP)?
• Can you set up the 1D DP state, transition, and base case cleanly?
• Do you handle unreachable amounts with a sentinel?

Why greedy doesn't work in general

Greedy ("always take the largest coin that fits") works for canonical currencies but not arbitrary sets. For coins = [1, 3, 4],amount = 6, greedy takes 4 + 1 + 1 = 3 coins; optimal is 3 + 3 = 2 coins. Always flag this in the interview — it's the reason DP is required.

DP solution — O(amount · len(coins)) time, O(amount) space

dp[i] = minimum coins to make amount i. Base case: dp[0] = 0. Transition: dp[i] = 1 + min(dp[i - c]) over all coins c with c ≤ i.

def coin_change(coins, amount):
    INF = amount + 1                             # sentinel > any real answer
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return dp[amount] if dp[amount] != INF else -1

Alternative — BFS view

You can also think of it as a shortest-path problem in an implicit graph: nodes are amounts, edges are coin denominations, we want the fewest steps from 0 to amount. BFS from 0 gives the same asymptotic complexity but is slightly cleaner conceptually when the interviewer wants a graph framing.

Complexity — what to say out loud

"Time O(amount × k) where k is the number of coin denominations. Space O(amount) for the DP table. Both are pseudo-polynomial — depend on the numeric value of amount, not just the input length."

Edge cases the interviewer will ask about

• Amount = 0 — return 0. Base case handles it.
• No coin can produce the amount — return -1. Sentinel comparison at the end.
• Amount smaller than every coin — same as above; return -1 unless amount is 0.
• Very large amount — pseudo-polynomial time can be slow; may need BFS with early termination or a smarter search.

Common follow-ups

• "Number of ways to make amount" — Different problem, still DP. ways[0] = 1; for each coin, ways[i] += ways[i - c]. Note: nested-loop order matters here (coins outer, amounts inner) to avoid counting permutations.
• "Coins have limited supply, not infinite." — Bounded knapsack variant; add a count dimension or use binary splitting to reduce to 0/1 knapsack.
• "Print the actual coins used." — Alongside dp[i], track which coin achieved the min; walk back from amount.

How to verbalize your answer

"Greedy doesn't work for arbitrary denominations, so it's DP. State is dp[i] = min coins for amount i. Base case dp[0] = 0. Transition: dp[i] = 1 + min over each coin c of dp[i − c] when c ≤ i. Sentinel value for unreachable amounts, return -1 at the end. Time O(amount · k), space O(amount)."