mafeshsho8lmafeshsho8l
Get Started
All coding questions

Coin Change

medium
Blind 75NeetCode 150dynamic-programming

Problem

Given coin denominations and a target amount, return the fewest coins needed to make exactly that amount. If it cannot be made, return negative one. You have an unlimited supply of each coin.

Examples

Input: coins = [1, 2, 5], amount = 11
Output: 3
5 + 5 + 1 uses three coins.
Input: coins = [2], amount = 3
Output: -1
Odd amounts are impossible with only twos.

Constraints

  • • 1 <= coins.length <= 12
  • • 1 <= coin value <= 2^31 - 1
  • • 0 <= amount <= 10^4
Hints(tap to reveal)
  • 1. Build the answer for every amount up to the target.
  • 2. Each amount tries every coin as the last one used.
Optimal approach(spoiler)
  1. Create a table of minimum coins for each amount from zero to target.
  2. Initialize amount zero to zero and the rest to infinity.
  3. For each amount, try every coin and relax from amount minus the coin.
  4. Return the table value at the target, or negative one if still infinite.
  5. O(amount * coins) time, O(amount) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor