Skip to main content

18. Coin Change

mediumAsked at Coinbase

Compute the fewest denominations to reach an exact value — Coinbase uses this DP classic to see how you model currency conversion and minimum-fee routing across crypto denominations.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 no combination can reach the amount, return -1. You have an unlimited supply of each denomination.

Constraints

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

Examples

Example 1

Input
coins = [1,5,10,25], amount = 41
Output
4

Explanation: 25 + 10 + 5 + 1 = 41 using 4 coins.

Example 2

Input
coins = [2], amount = 3
Output
-1

Approaches

1. Recursive with memoisation

For each amount, try every coin and recurse on the remainder; cache results to avoid recomputation.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const memo = new Map();
  function dp(rem) {
    if (rem === 0) return 0;
    if (rem < 0) return Infinity;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const c of coins) best = Math.min(best, 1 + dp(rem - c));
    memo.set(rem, best);
    return best;
  }
  const ans = dp(amount);
  return ans === Infinity ? -1 : ans;
}

Tradeoff:

2. Bottom-up DP (optimal)

Build a dp array where dp[i] = min coins for amount i. Iterate amounts 1..amount, try each coin.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i) dp[i] = Math.min(dp[i], 1 + dp[i - c]);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Coinbase-specific tips

Coinbase often frames this as a fee-minimisation question: given base-layer transaction fees as denominations, what is the cheapest path to a target settlement amount? They want to see you articulate the optimal substructure — that the cheapest way to reach amount i depends only on the cheapest way to reach i minus each denomination.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Coin Change and other Coinbase interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →