Skip to main content

20. Coin Change

mediumAsked at Mercury

Compute the fewest coins needed to make a target amount from given denominations.

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

Problem

Given an integer array coins and an amount, return the fewest number of coins needed to make up that amount. If the amount cannot be made, return -1; you may use each coin denomination 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,2,5], amount = 11
Output
3

Example 2

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

Approaches

1. Greedy largest-first

Subtract the largest coin that fits each iteration.

Time
O(amount)
Space
O(1)
coins.sort((a,b)=>b-a); let n=0;
for(const c of coins){ while(amount>=c){ amount-=c; n++;}}
return amount===0?n:-1; // breaks on coins=[1,3,4], amount=6

Tradeoff:

2. Bottom-up DP min table

dp[i] = min coins to make i; transition dp[i] = 1 + min(dp[i-c]) for each coin c <= i. Returns -1 when dp[amount] never improves.

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

Tradeoff:

Mercury-specific tips

Mercury uses coin-change framing for batch wire fee minimization — choose the smallest number of wire bundles (each with a denomination cap) to clear a sweep amount.

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

Practice these live with InterviewChamp.AI →