Skip to main content

322. Coin Change

medium

Find the fewest coins needed to make a given amount, or -1 if impossible. The classic unbounded-knapsack DP — easy to get wrong with greedy, clean with bottom-up DP.

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 of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

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

Explanation: 11 = 5 + 5 + 1.

Example 2

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

Example 3

Input
coins = [1], amount = 0
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Greedy (always take the largest coin) fails — e.g. coins = [1, 3, 4], amount = 6 — greedy picks 4 + 1 + 1, but 3 + 3 wins.

Hint 2

DP: dp[x] = min coins to make amount x. dp[0] = 0; dp[x] = 1 + min(dp[x - c] for c in coins if c <= x).

Hint 3

Initialize dp[1..amount] to amount + 1 (an impossibly large sentinel) so 'cannot make' propagates naturally; final return dp[amount] if it's <= amount else -1.

Solution approach

Reveal approach

Bottom-up DP. Allocate dp[0..amount] and initialize dp[0] = 0 and dp[i > 0] = amount + 1 (a sentinel larger than any valid answer). For x from 1 to amount: for each coin c with c <= x, dp[x] = min(dp[x], dp[x - c] + 1). After filling the table, return dp[amount] if it's <= amount else -1. The sentinel trick replaces explicit null/infinity handling and keeps the inner loop branch-free. O(amount * len(coins)) time, O(amount) space.

Complexity

Time
O(amount * n)
Space
O(amount)

Related patterns

  • dynamic-programming
  • unbounded-knapsack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Coin Change and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →