Coding Interview PatternsCoin Change
MediumDynamic Programming

Coin Change

Explanation & Solution

Practice Problem

Description

You are given an integer array coins representing coin denominations and an integer amount representing a total amount of money.

Return the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1.

You may assume you have an infinite supply of each kind of coin.

Input:coins = [1,5,10], amount = 12
0
1
1
5
2
10

Output: 3

Explanation: 12 = 10 + 1 + 1, which uses 3 coins.

Constraints

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

Approach

Dynamic Programming pattern

1. Define the Subproblem

  • Let dp[i] be the minimum number of coins needed to make amount i
  • We want to find dp[amount]

2. Establish the Base Case

  • dp[0] = 0 — zero coins are needed to make amount 0
  • Initialize all other entries to Infinity (meaning "not yet achievable")

3. Write the Recurrence

  • For each amount i from 1 to amount:
  • For each coin denomination c in coins:
  • If c <= i and dp[i - c] + 1 < dp[i], then dp[i] = dp[i - c] + 1
  • This means: if we use one coin of value c, the remaining amount i - c requires dp[i - c] coins

4. Build the Table Bottom-Up

  • Process amounts from 1 to amount in order
  • Each amount considers all coin denominations and takes the minimum
  • After the loop, dp[amount] contains the answer

5. Handle the Impossible Case

  • If dp[amount] is still Infinity, no combination of coins can form the target amount
  • Return -1 in that case; otherwise return dp[amount]

Key Insight

  • This is an unbounded knapsack variant solved with bottom-up DP
  • Each amount builds on previously solved smaller amounts
Time
O(amount * coins.length)nested loop over amounts and coins
Space
O(amount)one-dimensional DP array

Visualization

Input:
Dynamic Programmingcoins = [1,5,10], amount = 12
dp
—0—1—2—3—4—5—6—7—8—9—10—11—12

Press play to start DP animation

ComputingDependencyFilledEmpty
14 steps

Solution Code

Previous
House Robber II
Next
Coin Change II