Skip to main content

18. Coin Change

mediumAsked at Baidu

Find the fewest coins from a given set of denominations needed to make a target amount, or -1 if impossible.

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

Problem

Given an array of coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If no combination is possible, 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,2,5], amount=11
Output
3

Example 2

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

Approaches

1. Greedy by largest coin

Sort coins descending, subtract as many of the biggest as possible, repeat. Fails on [1,3,4] for amount=6.

Time
O(amount)
Space
O(1)
// Incorrect in general; commonly trotted out as the trap answer.

Tradeoff:

2. Bottom-up DP

dp[i] = min coins to reach i; for each amount i and coin c, dp[i] = min(dp[i], dp[i-c]+1).

Time
O(amount * coins)
Space
O(amount)
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 (i - c >= 0) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Baidu-specific tips

Baidu likes this for ad-ranking bid-allocation problems where greedy looks tempting but only DP gives the optimum, so be ready to give a counterexample showing greedy breaks within 30 seconds.

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

Practice these live with InterviewChamp.AI →