Skip to main content

18. Coin Change

mediumAsked at Coursera

Find the fewest coins that sum to a target amount, a bottom-up DP problem Coursera uses to assess dynamic programming skills relevant to course-scheduling optimization.

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

Problem

You are given an integer array coins representing coins of different denominations and an integer amount. Return the fewest number of coins needed to make up that amount. If the amount cannot be made up by any combination of coins, return -1.

Constraints

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

Examples

Example 1

Input
coins = [1,5,10], amount = 11
Output
2

Example 2

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

Approaches

1. Recursive DFS (no memo)

Try every coin at each step recursively — exponential time, times out for large amounts.

Time
O(S^n)
Space
O(n)
function coinChange(coins, amount) {
  if (amount === 0) return 0;
  let min = Infinity;
  for (const c of coins)
    if (c <= amount) {
      const res = coinChange(coins, amount - c);
      if (res !== -1) min = Math.min(min, res + 1);
    }
  return min === Infinity ? -1 : min;
}

Tradeoff:

2. Bottom-up DP

Build a dp array of size amount+1 where dp[i] = min coins for amount i. Fill from 1 to amount: dp[i] = min over all coins c where c<=i of dp[i-c]+1.

Time
O(S*n)
Space
O(S)
function coinChange(coins, amount) {
  const dp = 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 - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

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

Practice these live with InterviewChamp.AI →