Skip to main content

12. Coin Change

mediumAsked at Rappi

Compute the fewest coins needed to make a target amount — Rappi frames this as composing the minimum number of stacked courier surcharges to hit a promised payout.

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

Problem

Given coins of distinct denominations and a total amount, return the fewest coins needed 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. Recursive try-all

From the amount, recurse on amount - coin for every coin; pick the min.

Time
O(amount^coins)
Space
O(amount)
function rec(rem) {
  if (rem === 0) return 0;
  if (rem < 0) return -1;
  let best = Infinity;
  for (const c of coins) { const r = rec(rem - c); if (r >= 0) best = Math.min(best, r+1); }
  return best === Infinity ? -1 : best;
}

Tradeoff:

2. Bottom-up DP

Build dp[i] = min coins to make i, transitioning dp[i] = 1 + min(dp[i-c]) over each coin c.

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

Tradeoff:

Rappi-specific tips

Rappi flags candidates who jump to greedy — they want to hear you reject greedy explicitly because their surcharge denominations don't satisfy the matroid structure.

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

Practice these live with InterviewChamp.AI →