Coin Change Medium 0 attempts
LeetCode ↗

Coin Change

Medium Dynamic ProgrammingMemoization LeetCode

You have an unlimited supply of coins in the denominations given by array coins, and need to make up a target amount. Find the smallest number of coins that sum exactly to amount, or return -1 if no combination of the given coins can reach it.

Input Format
Implement coinChange(coins, amount). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

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

Example 3

Input
coins = [1]
amount = 0
Output
0
Constraints
  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
Test Cases (3)
Case 1
Args: [[1,2,5],11] Expected: 3
Case 2
Args: [[2],3] Expected: -1
Case 3
Args: [[1],0] Expected: 0
Topics
Dynamic ProgrammingMemoization

Bottom-Up DP

dp[i] = minimum coins for amount i.

javascript
function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(amount + 1);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

Time: O(amount × coins) | Space: O(amount)

Saved in this browser only. Private to you.

JavaScript