Skip to main content
Ace Hired
All coding problems

Coin Change: Minimum Coins

Mediumdynamic programmingBottom-up dynamic programming (unbounded knapsack)dynamic-programmingbottom-upunbounded-knapsack

Maintained by Vikas D, software engineer

You are handed a list of coin denominations and a target amount. Each denomination can be picked as many times as you like, and there is no limit on how many coins you spend. Your job is to hit the target exactly while using the smallest possible number of coins.

When several different mixes of coins all reach the target, only the count matters, so you want the mix with the fewest pieces. The specific coins chosen are not part of the answer.

If there is no way to land on the amount at all, return -1. An amount of zero is always reachable with zero coins, so that case answers 0.

Examples

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

5 + 5 + 1 sums to 11 with 3 coins. No two-coin combination reaches 11, so 3 is the minimum.

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

Every sum built from 2s is even, so an odd target like 3 can never be reached. The answer is -1.

Input: coins = [2, 5, 10, 1], amount = 27
Output: 4

10 + 10 + 5 + 2 reaches 27 with 4 coins, and no three coins from this set sum to 27.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
  • Each denomination may be used an unlimited number of times

Visible test cases

  • coinChange([1,5,11], 15) == 3
  • coinChange([2], 3) == -1
  • coinChange([1,2,5], 11) == 3
  • coinChange([1], 0) == 0
  • coinChange([2,5,10,1], 27) == 4

Hints

Hint 1

Picking the largest coin that fits at each step (a greedy choice) can overshoot the optimal count. With coins [1, 5, 11] and amount 15, grabbing 11 first leads to 11 + 1 + 1 + 1 + 1 = 5 coins, but 5 + 5 + 5 = 3 coins is better. You need to consider every coin at every sub-amount.

Hint 2

Define best[x] as the fewest coins that make exactly x. Then best[x] is 1 plus the smallest best[x - coin] over every coin that is not larger than x.

Hint 3

Build best from 0 up to amount so each value you need has already been computed. Start best[0] = 0 and mark every other entry as unreachable until a coin proves otherwise.

Loading the editor...

Approaches

Recursive search over coin choices

Time O(amount * coins.length) with memoization · Space O(amount) for the cache plus recursion depth

Try every denomination at each remaining amount and recurse on what is left, taking the cheapest branch. Memoize on the remaining amount so repeated sub-amounts are solved once.

  1. Write a helper that takes a remaining amount and returns the fewest coins to make it, or infinity if impossible.
  2. Base cases: remaining 0 returns 0, remaining negative returns infinity.
  3. For each coin, recurse on remaining minus that coin and keep the minimum result plus one.
  4. Cache each remaining amount's answer so it is not recomputed, then translate infinity at the top level into -1.

Bottom-up dynamic programming

Time O(amount * coins.length) · Space O(amount)

Fill a table best[0..amount] where best[x] is the minimum coins for x. Each entry is one more than the best of its reachable predecessors best[x - coin].

  1. Create an array best of length amount + 1, set every slot to a sentinel above amount, and set best[0] = 0.
  2. Loop x from 1 to amount; for each coin that is at most x, see if best[x - coin] + 1 beats the current best[x].
  3. After filling the table, best[amount] holds the answer if it is still at or below amount.
  4. If best[amount] is still the sentinel, no combination works, so return -1.

Common mistakes

  • Reaching for a greedy largest-coin-first strategy. It is correct for some coin systems but fails on sets like [1, 5, 11], so it will pass easy cases and break on adversarial ones.
  • Forgetting the amount = 0 case, which must return 0 rather than -1 or an out-of-bounds read.
  • Using 0 as the unreachable sentinel. A real best of 0 only belongs to amount 0, so mixing them up corrupts the table; use a value strictly above amount instead.
  • Returning the sentinel itself instead of converting unreachable amounts to -1.
  • Skipping the coin <= x check and reading best at a negative index.

Follow-up variations

  • Count the number of distinct coin combinations that make the amount instead of the minimum coin count.
  • Return one actual list of coins that achieves the minimum, not just its size.
  • Restrict each denomination to a finite supply, turning it into a bounded knapsack.
  • Handle very large amounts where an O(amount) table is too big, for instance with few denominations using number-theory shortcuts.

Recommended problems

Build the rest of your prep