Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Coin Change

Dynamic Programmingmedium

Implement `coinChange(coins, amount)` returning the fewest number of coins needed to make `amount`, or `-1` if it cannot be made.

Sample tests

Input: coinChange([1,2,5], 11)
Output: 3
Input: coinChange([2], 3)
Output: -1

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Greedy largest-coin-first fails for arbitrary coin sets.
  • Forgetting the unreachable case returns the wrong answer.

Learning resources

  • Wikipedia: Dynamic programming
Approach & explanation (try first)

Bottom-up DP over amounts gives the minimum coins in O(amount * coins) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.