Skip to main content

25. Coin Change

mediumAsked at Notion

Minimize the number of coins to reach an exact total using DP — a direct analogy to Notion's block-quota allocator, which must fill a usage limit with the fewest possible chunked operations of varying sizes.

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

Problem

Given an integer array coins representing coin denominations and a total amount, return the minimum number of coins needed to make up that amount. If the amount cannot be reached with any combination, return -1. You may use coins of each denomination any number of times.

Constraints

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

Examples

Example 1

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

Explanation: 15 = 5 + 5 + 5 (3 coins). Using 11+1+1+1+1 = 5 coins is worse.

Example 2

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

Approaches

1. Greedy (incorrect — shown for contrast)

Always pick the largest coin that fits. Fails on coins = [1,5,11], amount = 15 — greedy picks 11+1+1+1+1 = 5 coins vs. optimal 5+5+5 = 3.

Time
O(n log n + amount/minCoin)
Space
O(1)
// WARNING: greedy is WRONG for general coin sets.
// Shown to contrast with DP. Do not use in an interview.
function coinChangeGreedy(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a);
  let count = 0;
  let remaining = amount;
  for (const coin of sorted) {
    const use = Math.floor(remaining / coin);
    count += use;
    remaining -= use * coin;
  }
  return remaining === 0 ? count : -1;
}

Tradeoff:

2. Bottom-up DP

dp[i] = min coins to make amount i. For each amount from 1 to target, try every coin; dp[i] = min(dp[i], dp[i - coin] + 1).

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

Tradeoff:

Notion-specific tips

Notion uses this problem partly to catch greedy traps — open with the greedy counter-example (coins=[1,5,11], amount=15) to demonstrate you know when optimal substructure breaks down. Then walk through the DP recurrence. The -1 return for unreachable amounts is an easy miss — state the Infinity sentinel explicitly.

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

Practice these live with InterviewChamp.AI →