Skip to main content

22. Coin Change

mediumAsked at SoFi

Return the minimum number of coins needed to make up a given amount — SoFi loves this because it mirrors how a loan-amortization engine selects the smallest set of payments to clear principal.

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 that you need to make up that amount. If that amount cannot be made up by any combination of the coins, 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 (incorrect baseline)

Take the largest coin that fits, repeat — fails on cases like [1,3,4] target 6.

Time
O(amount)
Space
O(1)
function coinChange(coins, amount) {
  coins.sort((a,b)=>b-a);
  let count = 0;
  for (const c of coins) {
    while (amount >= c) { amount -= c; count++; }
  }
  return amount === 0 ? count : -1;
}

Tradeoff:

2. Bottom-up DP

dp[i] = min coins to make i. For each amount, try each coin and update dp[i] = min(dp[i], dp[i-c] + 1). Return dp[amount] or -1 if unreachable.

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

Tradeoff:

SoFi-specific tips

SoFi specifically watches for candidates who articulate why greedy fails and reach for DP — student-loan repayment optimizers face the same problem and must guarantee a true minimum, not a heuristic.

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

Practice these live with InterviewChamp.AI →