Skip to main content

18. Coin Change

mediumAsked at Monzo

Find the fewest coin denominations needed to fund a savings-goal top-up of exactly amount pence.

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

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins needed to make up that amount, or -1 if it cannot be made up by any combination.

Constraints

  • 1 <= coins.length <= 12
  • 0 <= amount <= 10^4
  • 1 <= coins[i] <= 2^31 - 1

Examples

Example 1

Input
coins = [1,2,5], amount = 11
Output
3

Example 2

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

Approaches

1. Recursion with memo

Recurse on remaining amount and memoize.

Time
O(amount * coins)
Space
O(amount)
const memo = new Map();
function f(rem) {
  if (rem < 0) return -1;
  if (rem === 0) return 0;
  if (memo.has(rem)) return memo.get(rem);
  let best = Infinity;
  for (const c of coins) { const s = f(rem - c); if (s >= 0) best = Math.min(best, s + 1); }
  const r = best === Infinity ? -1 : best;
  memo.set(rem, r);
  return r;
}

Tradeoff:

2. Bottom-up DP

Build dp[i] = fewest coins for amount i, transitioning from dp[i - c] for 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:

Monzo-specific tips

Monzo wants integer-pence arithmetic only — no floats — because savings-goal funding tolerates zero rounding error.

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

Practice these live with InterviewChamp.AI →