Coding problem · Medium · Dynamic Programming

Coin Change

Medium Algorithms & data structures Most askedSeen at Amazon, Google, Goldman Sachs, Bloomberg

Given coin denominations coins (unlimited supply of each) and an amount, return the fewest number of coins that make up that amount, or -1 if it can't be made.

Example 1

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

Example 2

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

Constraints

0 <= amount <= 10^4

Hints

Hint 1

Greedy (largest coin first) fails for coins like [1,3,4] and amount 6.

Hint 2

dp[a] = 1 + min(dp[a − c]) over coins c ≤ a.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(amount × coins) · Space O(amount)

Bottom-up DP: dp[0] = 0, every other amount starts at ∞. For each amount, try every coin and keep the minimum dp[a - c] + 1. If dp[amount] is still ∞, it's unreachable.

Reference solution

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

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

def coin_change(coins: list[int], amount: int) -> int:
    dp = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == float("inf") else int(dp[amount])

<?php

function coinChange(array $coins, int $amount): int
{
    $dp = array_fill(0, $amount + 1, PHP_INT_MAX);
    $dp[0] = 0;
    for ($a = 1; $a <= $amount; $a++) {
        foreach ($coins as $c) {
            if ($c <= $a && $dp[$a - $c] !== PHP_INT_MAX) {
                $dp[$a] = min($dp[$a], $dp[$a - $c] + 1);
            }
        }
    }
    return $dp[$amount] === PHP_INT_MAX ? -1 : $dp[$amount];
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a && dp[a - c] != Integer.MAX_VALUE) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

Common mistakes

Greedy coin choice — fails on non-canonical coin systems.