Coin Change Minimum Coins in DSA Java

Mental Model

We want to find the smallest number of coins needed to make a certain amount using given coin values. We try all possibilities and remember the best results to avoid repeating work.

Analogy: Imagine you have different sized jars of candies and you want to fill a bag with exactly a certain number of candies using the fewest jars possible. You try different jars and keep track of the best way to fill the bag for smaller amounts first.

Amount: 0 1 2 3 4 5
Coins: [1, 2, 5]
DP:    [0, ?, ?, ?, ?, ?]
↑
Start with 0 amount needing 0 coins.

Dry Run Walkthrough

Input: coins: [1, 2, 5], amount: 5

Goal: Find the minimum number of coins needed to make amount 5

Step 1: Initialize dp array with dp[0] = 0 and others as large number

dp: [0, ∞, ∞, ∞, ∞, ∞]

Why: 0 coins needed to make amount 0; others unknown yet

Step 2: Check amount 1: try coin 1 (1 ≤ 1), dp[1] = min(dp[1], dp[0] + 1) = 1

dp: [0, 1, ∞, ∞, ∞, ∞]

Why: Using coin 1, 1 coin needed for amount 1

Step 3: Check amount 2: try coin 1 (1 ≤ 2), dp[2] = min(dp[2], dp[1] + 1) = 2; try coin 2 (2 ≤ 2), dp[2] = min(2, dp[0] + 1) = 1

dp: [0, 1, 1, ∞, ∞, ∞]

Why: Using coin 2 is better for amount 2 (1 coin)

Step 4: Check amount 3: try coin 1 (1 ≤ 3), dp[3] = min(∞, dp[2] + 1) = 2; try coin 2 (2 ≤ 3), dp[3] = min(2, dp[1] + 1) = 2; try coin 5 (5 ≤ 3) no

dp: [0, 1, 1, 2, ∞, ∞]

Why: Minimum coins for 3 is 2 (1+2 or 1+1+1)

Step 5: Check amount 4: try coin 1 (1 ≤ 4), dp[4] = min(∞, dp[3] + 1) = 3; try coin 2 (2 ≤ 4), dp[4] = min(3, dp[2] + 1) = 2; try coin 5 (5 ≤ 4) no

dp: [0, 1, 1, 2, 2, ∞]

Why: Using two coins of 2 is better for amount 4

Step 6: Check amount 5: try coin 1 (1 ≤ 5), dp[5] = min(∞, dp[4] + 1) = 3; try coin 2 (2 ≤ 5), dp[5] = min(3, dp[3] + 1) = 3; try coin 5 (5 ≤ 5), dp[5] = min(3, dp[0] + 1) = 1

dp: [0, 1, 1, 2, 2, 1]

Why: Using coin 5 alone is best for amount 5

Result:

dp: [0, 1, 1, 2, 2, 1]
Minimum coins needed: 1

Annotated Code

DSA Java

import java.util.Arrays;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max); // fill with large number
        dp[0] = 0; // base case: 0 coins for amount 0

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); // update dp[i] if better
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount]; // if no solution, return -1
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        int result = coinChange(coins, amount);
        System.out.println("Minimum coins needed: " + result);
    }
}

Arrays.fill(dp, max); // fill with large number

initialize dp array with large values to represent impossible states

dp[0] = 0; // base case: 0 coins for amount 0

0 coins needed to make amount 0

for (int i = 1; i <= amount; i++) {

iterate over all amounts from 1 to target

for (int coin : coins) {

try each coin to see if it can improve the solution for amount i

if (coin <= i) {

only consider coins not larger than current amount

dp[i] = Math.min(dp[i], dp[i - coin] + 1); // update dp[i] if better

update dp[i] with minimum coins using current coin

return dp[amount] > amount ? -1 : dp[amount];

if dp[amount] is still large, no solution; else return minimum coins

Output

Minimum coins needed: 1

Complexity Analysis

Time: O(n * amount) because we check each coin for every amount up to target

Space: O(amount) for the dp array storing minimum coins for each amount

vs Alternative: Compared to recursive brute force which is exponential, this dynamic programming approach is efficient and avoids repeated calculations

Edge Cases

amount = 0

Returns 0 since no coins are needed

DSA Java

dp[0] = 0; // base case: 0 coins for amount 0

coins array empty

Returns -1 since no coins available to make any amount

DSA Java

return dp[amount] > amount ? -1 : dp[amount];

amount cannot be formed by given coins

Returns -1 indicating no solution

DSA Java

return dp[amount] > amount ? -1 : dp[amount];

When to Use This Pattern

When asked for the minimum number of items to reach a total using given denominations, use the coin change minimum coins pattern with dynamic programming to build solutions from smaller amounts.

Common Mistakes

Mistake: Not initializing dp array with a large number, causing incorrect minimum calculations
Fix: Initialize dp array with amount+1 or another large number to represent impossible states

Mistake: Forgetting to handle the base case dp[0] = 0
Fix: Set dp[0] = 0 explicitly to indicate zero coins needed for amount zero

Mistake: Returning dp[amount] directly without checking if solution exists
Fix: Return -1 if dp[amount] is still larger than amount, meaning no solution

Summary

Finds the minimum number of coins needed to make a given amount using given coin denominations.

Use when you need the fewest items to sum up to a target from a set of values.

Build the solution bottom-up by solving smaller amounts first and using those results to solve bigger amounts.

Practice

1. What does the Coin Change Minimum Coins problem ask you to find?
Given coins of different denominations and a total amount, find the minimum number of coins needed to make that amount.

easy

A. Minimum number of coins needed to make the amount

B. Maximum number of coins needed to make the amount

C. Number of ways to make the amount

D. Sum of all coin denominations

Solution

1. Step 1: Understand the problem statement

   The problem asks for the least number of coins needed to reach a given amount using available coin denominations.

2. Step 2: Differentiate from similar problems

   It is not about counting ways or maximum coins, but the minimum coins required.

3. Final Answer:

   Minimum number of coins needed to make the amount -> Option A

4. Quick Check:

   Minimum coins = minimum coins needed [OK]

Hint: Focus on 'minimum coins' needed, not ways or sums [OK]

Common Mistakes:

• Confusing minimum coins with number of ways
• Thinking about maximum coins instead of minimum
• Ignoring the total amount requirement

2. Which of the following Java method signatures correctly represents a function to find minimum coins for a given amount?

public static int minCoins(int[] coins, int amount)

easy

A. public int minCoins(int coins, int[] amount)

B. public static int minCoins(int[] coins, int amount)

C. static void minCoins(int[] coins, int amount)

D. public static int minCoins(int amount, int[] coins)

Solution

1. Step 1: Check parameter types and order

   The method should accept an array of coin denominations and an integer amount, in that order.

2. Step 2: Check return type and modifiers

   It should return an int representing minimum coins and be static for utility use.

3. Final Answer:

   public static int minCoins(int[] coins, int amount) -> Option B

4. Quick Check:

   Correct signature = public static int minCoins(int[] coins, int amount) [OK]

Hint: Array first, amount second; return int minimum coins [OK]

Common Mistakes:

• Swapping parameter order
• Wrong return type (void instead of int)
• Missing static keyword if utility method

3. What is the output of the following Java code?

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 6;
        System.out.println(minCoins(coins, amount));
    }
}

medium

A. -1

B. 3

C. 1

D. 2

Solution

1. Step 1: Understand the DP array filling

   dp[i] stores minimum coins for amount i. Initialized with max (7 here) except dp[0]=0.

2. Step 2: Calculate dp values for amount=6

   Using coins {1,3,4}: - dp[1] = 1 (1 coin of 1) - dp[2] = 2 (1+1) - dp[3] = 1 (coin 3) - dp[4] = 1 (coin 4) - dp[5] = 2 (4+1) - dp[6] = min(dp[6-1]+1=dp[5]+1=3, dp[6-3]+1=dp[3]+1=2, dp[6-4]+1=dp[2]+1=3) = 2

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Minimum coins for 6 = 2 [OK]

Hint: Trace dp array updates for each amount [OK]

Common Mistakes:

• Not initializing dp array correctly
• Returning dp[amount] without checking if solution exists
• Confusing dp indices or coin subtraction

4. Find the error in the following Java code snippet for minimum coin change:

public static int minCoins(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

medium

A. Using Integer.MAX_VALUE causes overflow when adding 1

B. dp array size should be amount, not amount + 1

C. dp[0] should be Integer.MAX_VALUE, not 0

D. The for loop should start from 0, not 1

Solution

1. Step 1: Identify the problem with Integer.MAX_VALUE

   Adding 1 to Integer.MAX_VALUE causes integer overflow, leading to incorrect dp values.

2. Step 2: Explain correct initialization

   Use a large number less than Integer.MAX_VALUE (like amount+1) to avoid overflow when adding 1.

3. Final Answer:

   Using Integer.MAX_VALUE causes overflow when adding 1 -> Option A

4. Quick Check:

   Integer.MAX_VALUE + 1 overflows [OK]

Hint: Avoid Integer.MAX_VALUE for dp initialization to prevent overflow [OK]

Common Mistakes:

• Ignoring overflow when adding 1 to max value
• Wrong dp array size
• Incorrect dp[0] initialization

5. Given coin denominations {2, 5, 10} and amount 7, what is the minimum number of coins needed? If not possible, return -1.
Use the Coin Change Minimum Coins approach.

medium

A. 1

B. 3

C. 2

D. -1

Solution

1. Step 1: Check possible combinations for amount 7

   Coins: 2, 5, 10 - 2+5=7 (2 coins) - 5+2=7 (2 coins) - 10 is too big But 2+5=7 is valid, so minimum coins = 2.

2. Step 2: Verify if amount 7 can be formed

   Actually, 2+5=7 is valid, so minimum coins = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   7 = 5 + 2 = 2 coins [OK]

Hint: Try largest coin first, then smaller coins [OK]

Common Mistakes:

• Assuming no solution without checking combinations
• Ignoring order of coins
• Returning -1 prematurely