Skip to main content

20. Coin Change

mediumAsked at Nubank

Compute the fewest coins that sum to a target amount; Nubank loves this one as a stand-in for cash-out denominations problems on PIX/withdrawal flows.

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

Problem

Given an integer array coins of denominations and an integer amount, return the minimum number of coins that sum exactly to amount. Return -1 if no combination works. You have an unlimited supply of each denomination.

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 by largest coin

Take as many of the largest coin as possible, recurse. Incorrect for arbitrary denomination sets (e.g., [1,3,4], amount 6).

Time
O(n)
Space
O(1)
// Sort desc; subtract greedily. Fails on coins=[1,3,4], amount=6 — greedy=4+1+1=3, optimal=3+3=2.

Tradeoff:

2. Bottom-up DP

dp[a] = min coins for amount a; transition dp[a] = 1 + min(dp[a - c]) over each coin c <= a. Fill 0..amount.

Time
O(amount * coins)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = 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 - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Nubank-specific tips

Nubank will press you to disprove the greedy with a counter-example — have one ready and write the DP cleanly; mention BRL denominations as the framing.

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

Practice these live with InterviewChamp.AI →