Skip to main content

18. Coin Change

mediumAsked at Riot Games

Find the fewest coins that sum to a target amount — Riot uses this DP pattern for RP-shop bundling and rune-page cost optimization.

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 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. Brute recursion

Try every coin at every subtotal, recursing into amount - coin.

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

Tradeoff:

2. Bottom-up DP

Build dp[i] = fewest coins to reach amount i by relaxing dp[i-c] + 1 across all coins. Same DP table Riot uses to find cheapest RP-bundle combinations for a given content-pack target.

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

Tradeoff:

Riot Games-specific tips

Riot grades whether you set dp[0]=0 with intent and explain why greedy fails for arbitrary coin sets — the same edge case their RP-bundling solver hits when content packs aren't power-of-two priced.

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

Practice these live with InterviewChamp.AI →