Coin Change in Java: Solution, Explanation & Practice

Minimum coins needed to make amount

Problem summary

Given coin denominations and a target amount, find the minimum number of coins needed to make that amount. Return -1 if impossible.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        
        // dp[i] = min coins needed for amount i
        // dp[i] = min(dp[i], dp[i-coin] + 1) for each coin
        // Print: Min coins: 3
    }
}

Expected output and test cases

[1,2,5], amount=11 → 5+5+1
```
Min coins: 3
```
[2], amount=3 → impossible
```
Min coins: -1
```
[1], amount=0 → 0 coins
```
Min coins: 0
```

Hints

Create dp array of size amount+1, initialize with infinity
dp[0] = 0 (0 coins needed for amount 0)
For each amount i, try each coin: dp[i] = min(dp[i], dp[i-coin]+1)
Only consider coin if i >= coin value

Validated solution

Reveal Java solution

import java.util.Arrays;

public class Main {
    static int minimumCoins(int[] coins, int amount) {
        int[] best = new int[amount + 1];
        Arrays.fill(best, amount + 1); best[0] = 0;
        for (int target = 1; target <= amount; target++) {
            for (int coin : coins) if (coin <= target) best[target] = Math.min(best[target], best[target - coin] + 1);
        }
        return best[amount] == amount + 1 ? -1 : best[amount];
    }
    public static void main(String[] args) { System.out.println("Min coins: " + minimumCoins(new int[] {1, 2, 5}, 11)); }
}

How to approach the problem

best[target] stores the fewest coins needed for that amount. Start every unknown amount at an impossible sentinel, then improve it from each reachable amount target - coin.

Approach

Set best[0] to zero.
Use a sentinel larger than any possible answer.
For every target, try each denomination that fits.

Time and space complexity

Time: O(amount * number of coins). Space: O(amount).

Edge cases to test

Amount zero needs zero coins.
An unreachable amount must remain distinguishable from a valid large answer.

Common mistakes

Using a greedy largest-first choice, which fails for some coin systems.
Adding one to an unreachable sentinel without choosing it safely.

Follow-up challenge

Reconstruct one optimal set of coins, not only its count.

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler