Skip to main content

13. Coin Change

mediumAsked at JetBrains

Find the minimum number of coins to make a given amount — JetBrains uses this to gauge bottom-up DP discipline before tackling cost-driven refactor recommenders.

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

Problem

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

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 under the remaining amount repeatedly; fails for non-canonical sets (e.g., [1,3,4] amount 6).

Time
O(amount/min)
Space
O(1)
// counterexample: coins=[1,3,4], amount=6 → greedy says 4+1+1 (3); optimal is 3+3 (2)

Tradeoff:

2. Bottom-up DP

dp[a] = min coins for amount a; iterate a from 1 to amount, try each coin. Linear-product space and time, no recursion. Mirrors JetBrains's bounded-cost refactor scoring.

Time
O(amount * coins)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) if (a - c >= 0) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to dismiss greedy with a concrete counterexample — they reward candidates who actively falsify the obvious wrong approach the way their inspection engine validates fix suggestions.

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

Practice these live with InterviewChamp.AI →