Code Logo

Coin Change

Published at24 Jul 2026
Created by
Medium 0 views
Like0

You are given an integer array coins representing different 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 that you have an infinite number of each kind of coin.

This is the classic unbounded knapSack DP problem. The DP array dp[i] stores the minimum coins needed to make amount i. The base case is dp[0] = 0. For each amount from 1 to the target, try each coin denomination and take the minimum: dp[i] = min(dp[i], dp[i - coin] + 1).

The inner loop iterates over coin denominations. For each coin that is not larger than the current amount, check if using that coin leads to a smaller coin count. The time complexity is O(amount * coins) and space is O(amount). This is a bottom-up DP that builds solutions from smaller subproblems to larger ones.

Edge cases include amount = 0 (return 0), no coin combination possible (return -1), and very large amounts where the DP array may need careful sizing.

The unbounded knapSack structure of coin change allows unlimited use of each denomination. The DP array builds solutions incrementally: to make amount i, try subtracting each coin and adding one to the solution for the remainder. This bottom-up approach ensures all subproblems are solved before being needed.

Example Input & Output

Example 1
Input
[1,2,5], 11
Output
3
Explanation

5+5+1 uses 3 coins.

Example 2
Input
[1], 0
Output
0
Explanation

Zero amount needs no coins.

Example 3
Input
[5,10], 25
Output
3
Explanation

10+10+5 uses 3 coins.

Example 4
Input
[1,2,3], 6
Output
2
Explanation

3+3 uses 2 coins.

Example 5
Input
[2], 3
Output
-1
Explanation

Cannot make 3 with only coin 2.

Algorithm Flow

Recommendation Algorithm Flow for Coin Change
Recommendation Algorithm Flow for Coin Change

Solution Approach

DP array of size amount+1. Initialize with a large number. For each coin, update dp[i] = min(dp[i], dp[i-coin] + 1).

function solution(coins, amount) {
  var dp = new Array(amount + 1);
  dp[0] = 0;
  for (var i = 1; i <= amount; i++) {
    dp[i] = amount + 1;
    for (var j = 0; j < coins.length; j++) {
      if (coins[j] <= i) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

Time O(amount * coins), Space O(amount).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int c : coins) {
                if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}