Coin Change Minimum Coins in DSA Java - Execution Trace

Concept Flow - Coin Change Minimum Coins

Start with amount

↓

Initialize DP array with max values

↓

Set dp[0

↓

For each coin

↓

For each amount from coin to target

↓

Update dp[amount

↓

Repeat for all coins and amounts

↓

Check dp[target

↓

If dp[target

↓

End

We build a table dp where dp[i] stores the minimum coins needed for amount i. We update dp by checking all coins for each amount.

Execution Sample

DSA Java

int[] coins = {1, 2, 5};
int amount = 11;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
  for (int i = coin; i <= amount; i++) {
    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  }
}

This code finds the minimum number of coins needed to make amount 11 using coins 1, 2, and 5.

Execution Table

Step	Operation	Amount Index (i)	Coin Used	dp[i] Before	dp[i - coin]	dp[i] After	dp Array Snapshot
1	Initialize dp array	-	-	-	-	-	[12,12,12,12,12,12,12,12,12,12,12,12]
2	Set dp[0] = 0	0	-	-	-	0	[0,12,12,12,12,12,12,12,12,12,12,12]
3	Use coin 1	1	1	12	dp[0]=0	1	[0,1,12,12,12,12,12,12,12,12,12,12]
4	Use coin 1	2	1	12	dp[1]=1	2	[0,1,2,12,12,12,12,12,12,12,12,12]
5	Use coin 1	3	1	12	dp[2]=2	3	[0,1,2,3,12,12,12,12,12,12,12,12]
6	Use coin 1	4	1	12	dp[3]=3	4	[0,1,2,3,4,12,12,12,12,12,12,12]
7	Use coin 1	5	1	12	dp[4]=4	5	[0,1,2,3,4,5,12,12,12,12,12,12]
8	Use coin 1	6	1	12	dp[5]=5	6	[0,1,2,3,4,5,6,12,12,12,12,12]
9	Use coin 1	7	1	12	dp[6]=6	7	[0,1,2,3,4,5,6,7,12,12,12,12]
10	Use coin 1	8	1	12	dp[7]=7	8	[0,1,2,3,4,5,6,7,8,12,12,12]
11	Use coin 1	9	1	12	dp[8]=8	9	[0,1,2,3,4,5,6,7,8,9,12,12]
12	Use coin 1	10	1	12	dp[9]=9	10	[0,1,2,3,4,5,6,7,8,9,10,12]
13	Use coin 1	11	1	12	dp[10]=10	11	[0,1,2,3,4,5,6,7,8,9,10,11]
14	Use coin 2	2	2	2	dp[0]=0	1	[0,1,1,3,4,5,6,7,8,9,10,11]
15	Use coin 2	3	2	3	dp[1]=1	2	[0,1,1,2,4,5,6,7,8,9,10,11]
16	Use coin 2	4	2	4	dp[2]=1	2	[0,1,1,2,2,5,6,7,8,9,10,11]
17	Use coin 2	5	2	5	dp[3]=2	3	[0,1,1,2,2,3,6,7,8,9,10,11]
18	Use coin 2	6	2	6	dp[4]=2	3	[0,1,1,2,2,3,3,7,8,9,10,11]
19	Use coin 2	7	2	7	dp[5]=3	4	[0,1,1,2,2,3,3,4,8,9,10,11]
20	Use coin 2	8	2	8	dp[6]=3	4	[0,1,1,2,2,3,3,4,4,9,10,11]
21	Use coin 2	9	2	9	dp[7]=4	5	[0,1,1,2,2,3,3,4,4,5,10,11]
22	Use coin 2	10	2	10	dp[8]=4	5	[0,1,1,2,2,3,3,4,4,5,5,11]
23	Use coin 2	11	2	11	dp[9]=5	6	[0,1,1,2,2,3,3,4,4,5,5,6]
24	Use coin 5	5	5	3	dp[0]=0	1	[0,1,1,2,2,1,3,4,4,5,5,6]
25	Use coin 5	6	5	3	dp[1]=1	2	[0,1,1,2,2,1,2,4,4,5,5,6]
26	Use coin 5	7	5	4	dp[2]=1	2	[0,1,1,2,2,1,2,2,4,5,5,6]
27	Use coin 5	8	5	4	dp[3]=2	3	[0,1,1,2,2,1,2,2,3,5,5,6]
28	Use coin 5	9	5	5	dp[4]=2	3	[0,1,1,2,2,1,2,2,3,3,5,6]
29	Use coin 5	10	5	5	dp[5]=1	2	[0,1,1,2,2,1,2,2,3,3,2,6]
30	Use coin 5	11	5	6	dp[6]=2	3	[0,1,1,2,2,1,2,2,3,3,2,3]

💡 dp[11] = 3 means minimum 3 coins needed for amount 11

Variable Tracker

Variable	Start	After Step 2	After Step 13	After Step 24	After Step 30	Final
dp	[12,12,12,12,12,12,12,12,12,12,12,12]	[0,12,12,12,12,12,12,12,12,12,12,12]	[0,1,2,3,4,5,6,7,8,9,10,11]	[0,1,1,2,2,1,3,4,4,5,5,6]	[0,1,1,2,2,1,2,2,3,3,2,3]	[0,1,1,2,2,1,2,2,3,3,2,3]
coin	-	-	1	5	5	-
i	-	0	11	5	11	-

Key Moments - 3 Insights

Why do we initialize dp array with amount+1 (a large number)?

We use amount+1 as a placeholder for 'infinity' because no solution can need more coins than amount itself. This helps us find minimum values correctly as shown in execution_table rows 1 and 2.

Why is dp[0] set to 0 at the start?

dp[0] = 0 means zero coins are needed to make amount zero. This is the base case that allows building solutions for larger amounts, as seen in execution_table row 2.

How does dp[i] get updated when using each coin?

For each amount i, dp[i] is updated to the minimum of its current value and dp[i - coin] + 1. This means we try to use the current coin and add one coin to the best solution for amount i - coin. See execution_table rows 14-30 for examples.

Visual Quiz - 3 Questions

Look at the execution_table at step 14, what is dp[2] after using coin 2?

A 12

B 1

C 2

D 0

💡 Hint

Check the 'dp[i] After' column for step 14 where i=2 and coin=2

At which step does dp[5] first get updated to 1?

A Step 7

B Step 17

C Step 24

D Step 29

💡 Hint

Look for dp[5] 'dp[i] After' column changes in execution_table rows involving coin 5

If we remove coin 1 from the coins array, how would dp[1] change after initialization?

A dp[1] would remain 12 (no update)

B dp[1] would become 1

C dp[1] would become 0

D dp[1] would become 2

💡 Hint

Without coin 1, dp[1] cannot be updated from initial max value as no coin fits amount 1

Concept Snapshot

Coin Change Minimum Coins:
- Use dp array of size amount+1
- Initialize dp with amount+1 (infinity), dp[0]=0
- For each coin, update dp[i] = min(dp[i], dp[i-coin]+1)
- dp[amount] gives min coins or no solution if unchanged
- Bottom-up dynamic programming approach

Full Transcript

The Coin Change Minimum Coins problem finds the least number of coins needed to make a target amount using given coin denominations. We create a dp array where dp[i] represents the minimum coins needed for amount i. Initially, dp is filled with a large number (amount+1) to represent no solution, except dp[0] which is zero since zero coins are needed for amount zero. We then iterate over each coin and for each amount from coin value up to the target amount, we update dp[i] by choosing the minimum between the current dp[i] and dp[i - coin] + 1. This process builds up solutions for all amounts until dp[amount] holds the minimum coins needed. If dp[amount] remains the large initial value, it means no combination of coins can make that amount. The execution table shows step-by-step how dp array values change as coins are processed, and the variable tracker follows dp and loop variables. Key moments clarify why dp is initialized with amount+1, why dp[0] is zero, and how dp updates work. The visual quiz tests understanding of dp updates and effects of coin removal.

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