Skip to main content

23. Coin Change

mediumAsked at Udemy

Find the fewest coins needed to make a target amount — Udemy uses bottom-up DP here to evaluate dynamic-programming fundamentals for coupon and discount optimization problems.

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

Problem

Given an array of coin denominations and an integer amount, return the minimum number of coins needed to make up that amount. If no combination can reach the amount, return -1. You may use each coin an unlimited number of times.

Constraints

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

Examples

Example 1

Input
coins = [1,5,11], amount = 15
Output
3

Example 2

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

Approaches

1. Recursive with memoization

Top-down DP: recursively subtract each coin and cache results in a memo map.

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

Tradeoff:

2. Bottom-up DP table

Build dp[0..amount] where dp[i] = min coins for amount i; initialize to Infinity, set dp[0]=0, and for each amount try subtracting every coin denomination.

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], dp[i - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Udemy-specific tips

Udemy asks about e-learning recommendation systems, content search, and marketplace algorithms — balanced mix of arrays, hash maps, and dynamic programming problems.

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 Udemy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →