Skip to main content

21. Coin Change

mediumAsked at Coupang

Compute the fewest coins to make an amount, mirroring how Coupang's checkout engine selects the minimum-count promotion stack to reach a target Korean e-commerce search ranking discount.

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

Problem

Given an integer array coins of denominations and an integer amount, return the fewest number of coins to make up that amount. Return -1 if impossible.

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

Take the largest coin that fits each step (FAILS for non-canonical sets).

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

Tradeoff:

2. Bottom-up DP

dp[i] = min coins to make i. For each i, try every denomination and pick the min of dp[i - coin] + 1.

Time
O(amount * len(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:

Coupang-specific tips

Coupang's checkout engine stacks promotions to hit a target discount with the fewest coupons; DP over coin denominations is the canonical pattern, and the greedy trap is a classic interview tell at this team.

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

Practice these live with InterviewChamp.AI →