Code Logo

Coin Change

Published at24 Jul 2026
Created by
Medium 1 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

Solution Approach

Given a target amount and an array of coin denominations, find the minimum number of coins needed to make up that amount. Use dynamic programming where dp[i] represents the minimum coins needed for amount i. Initialize dp[0]=0 and all other amounts to Infinity. For each amount from 1 to target, try each coin and take the minimum.

function coinChange(coins, amount) {
  var dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (var i = 1; i <= amount; i++) {
    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] === Infinity ? -1 : dp[amount];
}

The recurrence checks: for each coin, if we use it, the remaining amount is i - coins[j], and we add 1 coin to the optimal solution for that remaining amount. The minimum across all coins is the answer for amount i.

Time complexity is O(amount * coins), space complexity is 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];
    }
}