Command Palette

Search for a command to run...

Hectal
Problem 30.4 · Knapsack DPMedium

Coin Change

PatternKnapsack DPGraph BFS

What it teaches: Unbounded knapsack minimising the number of items.

Practise it on judges as “Coin Change”.

The problem

Return the fewest coins (unlimited of each type) that make up amount, or −1 if impossible.

Example 1

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

5 + 5 + 1.

Constraints

  • 1 ≤ coins ≤ 12
  • 0 ≤ amount ≤ 10⁴

Pattern clues in the wording

  • → Fewest items to reach a sum, items reusable

These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int coinChange(int[] coins, int amount) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
coins = [1,2,5]
amount = 11
3
2
coins = [2]
amount = 3
-1
3
coins = [1]
amount = 0
0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Unbounded min DP · O(amount × coins)
1

Unbounded min DP

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

best[0] = 0, others = amount + 1 (acts as ∞). For each amount a, try every coin.

Approach 1
import java.util.Arrays;

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

Verdict: Standard.

Before you submit

Edge cases and common mistakes

Test these inputs

  • amount = 0 (0 coins)
  • Impossible amount (−1)

Mistakes people make

  • Greedy largest-coin-first.
  • Using Integer.MAX_VALUE and overflowing on + 1.

Interview

Follow-up questions

How is this a shortest-path problem?