ntree.ai
ntree.aiCoin Change

Solutions

1. Recursion

O(nᵃ) time | O(a) space, for n coins and amount a

Intuition

We can try each coin one by one, subtracting its value from the amount and repeating the same for the amount left. When the amount becomes zero, that is the combination of coins that add up to the original amount.

Algorithm

  1. Return 0 for an amount of 0.
  2. Iterate through the loop from the first coin to the last coin, skipping any coin greater than the amount.
    • Call coinChange again with the amount left once the coin is taken.
    • Keep the smallest answer found so far, plus one for the coin.
  3. Return the smallest, or -1 when the amount cannot be made.
1
3
4
coinChange(5)
coinChange(4)
coinChange(3)
coinChange(2)
coinChange(1)
coinChange(0)
coinChange(0)
coinChange(1)
coinChange(0)
coinChange(0)
coinChange(2)
coinChange(1)
coinChange(0)
coinChange(1)
coinChange(0)
coinChange(5) = 1 + min(coinChange(4), coinChange(2), coinChange(1))
1 / 25

Code

Code
Python
def coinChange(coins: list[int], amount: int) -> int:
    if amount == 0:
        return 0
    best = -1
    for coin in coins:
        if coin > amount:
            continue
        rest = coinChange(coins, amount - coin)
        if rest >= 0 and (best < 0 or rest + 1 < best):
            best = rest + 1
    return best
/**
 * @param {number[]} coins
 * @param {number} amount
 * @returns {number}
 */
var coinChange = function (coins, amount) {
  if (amount === 0) return 0
  let best = -1
  for (const coin of coins) {
    if (coin > amount) continue
    const rest = coinChange(coins, amount - coin)
    if (rest >= 0 && (best < 0 || rest + 1 < best)) best = rest + 1
  }
  return best
}
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int best = -1;
        for (int coin : coins) {
            if (coin > amount) continue;
            int rest = coinChange(coins, amount - coin);
            if (rest >= 0 && (best < 0 || rest + 1 < best)) best = rest + 1;
        }
        return best;
    }
}

2. Dynamic Programming, Top Down

O(n * a) time | O(a) space, for n coins and amount a

Intuition

We can try each coin one by one, subtracting its value from the amount and repeating the same for the amount left. When the amount becomes zero, that is the combination of coins that add up to the original amount.

To avoid repeating the same calls, we can store the fewest coins for each amount in a hash map.

Algorithm

  1. Create a change function taking the coins, an amount and a hash map.
    • Return the value from the hash map for the amount when it is there.
    • Otherwise call change again for every coin that is not greater than the amount, keeping the smallest answer found plus one, or -1 when the amount cannot be made.
    • Store that under the amount in the hash map and return it.
  2. Return change called with the coins, the input amount and a hash map holding 0 for an amount of 0.
1
3
4
coinChange(5)
coinChange(4)
coinChange(3)
coinChange(2)
coinChange(1)
coinChange(0)
coinChange(0)
coinChange(1)
coinChange(0)
coinChange(2)
coinChange(1)
0→0
11
22
31
41
52
coinChange(5) = 1 + min(coinChange(4), coinChange(2), coinChange(1))
1 / 17

Code

Code
Python
def coinChange(coins: list[int], amount: int) -> int:
    return change(coins, amount, {0: 0})


def change(coins: list[int], amount: int, known: dict[int, int]) -> int:
    if amount in known:
        return known[amount]
    best = -1
    for coin in coins:
        if coin > amount:
            continue
        restCoins = change(coins, amount - coin, known)
        if restCoins >= 0 and (best < 0 or restCoins + 1 < best):
            best = restCoins + 1
    known[amount] = best
    return best
/**
 * @param {number[]} coins
 * @param {number} amount
 * @returns {number}
 */
var coinChange = function (coins, amount) {
  return change(coins, amount, new Map([[0, 0]]))
}

function change(coins, amount, known) {
  if (known.has(amount)) return known.get(amount)
  let best = -1
  for (const coin of coins) {
    if (coin > amount) continue
    const restCoins = change(coins, amount - coin, known)
    if (restCoins >= 0 && (best < 0 || restCoins + 1 < best)) best = restCoins + 1
  }
  known.set(amount, best)
  return best
}
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int coinChange(int[] coins, int amount) {
        Map<Integer, Integer> known = new HashMap<>();
        known.put(0, 0);
        return coinChange(coins, amount, known);
    }

    private int coinChange(int[] coins, int amount, Map<Integer, Integer> known) {
        Integer stored = known.get(amount);
        if (stored != null) return stored;
        int best = -1;
        for (int coin : coins) {
            if (coin > amount) continue;
            int rest = coinChange(coins, amount - coin, known);
            if (rest >= 0 && (best < 0 || rest + 1 < best)) best = rest + 1;
        }
        known.put(amount, best);
        return best;
    }
}

3. Dynamic Programming, Bottom Up

O(n * a) time | O(a) space, for n coins and amount a

Intuition

We can calculate the fewest coins needed to add up to every number starting from 1 up to the input amount.

For each amount we subtract each coin one by one, where the fewest coins needed is one plus the fewest coins needed for the smaller amount that was already calculated.

Algorithm

  1. Create an array holding the fewest coins for every amount from 0 up to the input amount, with 0 needing no coins and every other amount filled with a count greater than any real answer.
  2. Iterate through the outer loop from the amount 1 up to the input amount.
  3. For each outer loop iteration, iterate through the inner loop from the first coin to the last coin, skipping any coin greater than that amount.
  4. Calculate the smaller amount by subtracting that coin's value.
  5. Keep the smaller of what the array already holds for that amount and one more than what it holds for the smaller amount.
  6. Return the element for the input amount, or -1 when it still holds the larger count.
1
3
4
0
012345
an amount of 0 needs no coins
1 / 12

Code

Code
Python
def coinChange(coins: list[int], amount: int) -> int:
    fewest = [0] + [amount + 1] * amount
    for target in range(1, amount + 1):
        for coin in coins:
            if coin <= target:
                fewest[target] = min(fewest[target], fewest[target - coin] + 1)
    return fewest[amount] if fewest[amount] <= amount else -1
/**
 * @param {number[]} coins
 * @param {number} amount
 * @returns {number}
 */
var coinChange = function (coins, amount) {
  const fewest = new Array(amount + 1).fill(amount + 1)
  fewest[0] = 0
  for (let target = 1; target <= amount; target++) {
    for (const coin of coins) {
      if (coin <= target) {
        fewest[target] = Math.min(fewest[target], fewest[target - coin] + 1)
      }
    }
  }
  return fewest[amount] <= amount ? fewest[amount] : -1
}
import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] fewest = new int[amount + 1];
        Arrays.fill(fewest, amount + 1);
        fewest[0] = 0;
        for (int target = 1; target <= amount; target++) {
            for (int coin : coins) {
                if (coin <= target) {
                    fewest[target] = Math.min(fewest[target], fewest[target - coin] + 1);
                }
            }
        }
        return fewest[amount] <= amount ? fewest[amount] : -1;
    }
}
def coinChange(coins: list[int], amount: int) -> int:
    pass
 

Press Visualise to step through your code.