Skip to main content

19. Coin Change

mediumAsked at Postman

Return the fewest number of coins needed to make up an amount, or -1 if impossible.

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

Problem

You are given an integer array of coin denominations and an integer amount. Return the fewest coins needed to make amount, or -1 if the amount cannot be made up. You have an infinite supply of each coin.

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

Repeatedly take the largest coin that fits; works for canonical sets like USD but is wrong for general sets.

Time
O(amount)
Space
O(1)
// counter-example: coins=[1,3,4], amount=6 -> greedy gives 3 (4+1+1) instead of 2 (3+3)

Tradeoff:

2. Bottom-up DP

dp[a] = min coins to make a. dp[a] = min over c in coins of dp[a-c] + 1. Initialize dp[0]=0 and rest to Infinity.

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 a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a) dp[a] = Math.min(dp[a], dp[a-c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Postman-specific tips

Postman wants you to call out why greedy fails — they care about the analogy to API rate-limit token bucketing where naive greedy allocation under-utilizes the budget.

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

Practice these live with InterviewChamp.AI →