Back to ChallengesCoin Change (Minimum Coins)Easy 25 min

Coin Change (Minimum Coins)

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 it is impossible, return -1.

Examples

Input: coins = [1,2,5], amount = 11

Output: 3

11 = 5 + 5 + 1

Input: coins = [2], amount = 3

Output: -1

3 cannot be made up using only 2.

Constraints

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

Complexity Analysis

Time

O(amount * coins.length)

compute min coin counts up to target amount.

Space

O(amount)

DP table size.

Test Cases

#1 Optimal combination

Input: [1,2,5], 11

Expected: 3

#2 Impossible case

Input: [2], 3

Expected: -1

#3 Zero amount

Input: [1], 0

Expected: 0

#4 Larger denominations

Input: [186,419,83,408], 6249

Expected: 20

JavaScript

Output

Click "Run Code" to see output here...