Coin Change Minimum Coins in DSA Go

Mental Model

Find the smallest number of coins needed to make a target amount using given coin values. We build up solutions from smaller amounts to the target.

Analogy: Imagine you want to pay a certain amount using the fewest bills or coins from your wallet. You try to pay smaller amounts first and remember the best way to pay each amount, then use that to pay the bigger amount.

coins: [1, 3, 4]
amount: 6

We find min coins for 0 -> 1 -> 2 -> ... -> 6

DP array:
index: 0  1  2  3  4  5  6
value: 0  1  2  1  1  2  2

Dry Run Walkthrough

Input: coins: [1, 3, 4], amount: 6

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

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: Calculate dp[1]: try coin 1 (1 ≤ 1), dp[1] = min(dp[1], dp[0]+1) = 1

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

Why: 1 coin of 1 makes amount 1

Step 3: Calculate dp[2]: try coin 1 (1 ≤ 2), dp[2] = min(∞, dp[1]+1) = 2

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

Why: two coins of 1 make amount 2

Step 4: Calculate dp[3]: try coins 1 and 3; dp[3] = min(∞, dp[2]+1, dp[0]+1) = 1

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

Why: one coin of 3 makes amount 3

Step 5: Calculate dp[4]: try coins 1,3,4; dp[4] = min(∞, dp[3]+1, dp[1]+1, dp[0]+1) = 1

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

Why: one coin of 4 makes amount 4

Step 6: Calculate dp[5]: try coins 1,3,4; dp[5] = min(∞, dp[4]+1, dp[2]+1, dp[1]+1) = 2

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

Why: two coins (e.g., 4+1) make amount 5

Step 7: Calculate dp[6]: try coins 1,3,4; dp[6] = min(∞, dp[5]+1, dp[3]+1, dp[2]+1) = 2

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

Why: two coins (e.g., 3+3) make amount 6

Result:

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

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

func minCoins(coins []int, amount int) int {
	dp := make([]int, amount+1)
	dp[0] = 0
	for i := 1; i <= amount; i++ {
		dp[i] = math.MaxInt32
	}

	for i := 1; i <= amount; i++ {
		for _, coin := range coins {
			if coin <= i && dp[i-coin] != math.MaxInt32 {
				if dp[i] > dp[i-coin]+1 {
					dp[i] = dp[i-coin] + 1
				}
			}
		}
	}

	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}

func main() {
	coins := []int{1, 3, 4}
	amount := 6
	result := minCoins(coins, amount)
	fmt.Printf("Minimum coins needed: %d\n", result)
}

dp[0] = 0

initialize dp[0] before setting others to MaxInt32

for i := 1; i <= amount; i++ {

iterate through all amounts from 1 to target

for _, coin := range coins {

try each coin to see if it can contribute to current amount

if coin <= i && dp[i-coin] != math.MaxInt32 {

check if coin can be used and previous amount is reachable

if dp[i] > dp[i-coin]+1 {

update dp[i] if using this coin reduces coin count

dp[i] = dp[i-coin] + 1

store new minimum coins for amount i

if dp[amount] == math.MaxInt32 {

check if amount is unreachable

return dp[amount]

return minimum coins needed

Output

Minimum coins needed: 2

Complexity Analysis

Time: O(n*m) where n is amount and m is number of coins, because we compute dp for each amount checking all coins

Space: O(n) for dp array storing minimum coins for each amount up to target

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

Edge Cases

amount is 0

returns 0 because no coins are needed

DSA Go

dp[0] = 0

no coins given

returns -1 because no amount can be formed

DSA Go

if dp[amount] == math.MaxInt32 { return -1 }

amount cannot be formed by given coins

returns -1 indicating no solution

DSA Go

if dp[amount] == math.MaxInt32 { return -1 }

When to Use This Pattern

When you need to find the minimum number of items to reach a target sum 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 for unreachable amounts
Fix: Initialize dp[i] with a large number like math.MaxInt32 to represent unreachable states

Mistake: Not checking if dp[i-coin] is reachable before using it
Fix: Add condition dp[i-coin] != math.MaxInt32 before updating dp[i]

Mistake: Returning dp[amount] without checking if amount is reachable
Fix: Check if dp[amount] == math.MaxInt32 and return -1 if unreachable

Summary

Finds the fewest coins needed to make a target amount from given coin values.

Use when you want to minimize the number of coins or items to reach a sum.

Build solutions from smaller amounts up to the target using dynamic programming.

Practice

1. What does the "Coin Change Minimum Coins" problem ask you to find?

easy

A. The smallest number of coins needed to make a given amount

B. The total number of different coins available

C. The largest coin value in the list

D. The sum of all coin values

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of coins needed to make a specific amount using given coin denominations.

2. Step 2: Identify the correct description

   The smallest number of coins needed to make a given amount correctly describes this goal, while others describe unrelated concepts.

3. Final Answer:

   The smallest number of coins needed to make a given amount -> Option A

4. Quick Check:

   Minimum coins = smallest count needed [OK]

Hint: Focus on 'minimum coins' needed for the amount [OK]

Common Mistakes:

• Confusing total coin count with minimum coins
• Thinking it's about coin values sum
• Mixing largest coin with minimum coins

2. Which Go code snippet correctly initializes a slice to store minimum coins for amounts up to 5 with initial value 6 (assuming 6 means unreachable)?

easy

A. minCoins := make([]int, 6); for i := 0; i <= 6; i++ { minCoins[i] = 6 }

B. minCoins := []int{6,6,6,6,6}

C. minCoins := make([]int, 5); for i := 0; i < 5; i++ { minCoins[i] = 6 }

D. minCoins := make([]int, 6); for i := range minCoins { minCoins[i] = 6 }

Solution

1. Step 1: Check slice length and initialization

   We need a slice of length 6 (for amounts 0 to 5). minCoins := make([]int, 6); for i := range minCoins { minCoins[i] = 6 } creates a slice of length 6 and sets each element to 6 using a loop.

2. Step 2: Verify correctness of other options

   minCoins := []int{6,6,6,6,6} creates length 5 (too short); minCoins := make([]int, 5); for i := 0; i < 5; i++ { minCoins[i] = 6 } creates length 5 (too short); minCoins := make([]int, 6); for i := 0; i <= 6; i++ { minCoins[i] = 6 } loops out of range (index 6 invalid).

3. Final Answer:

   minCoins := make([]int, 6); for i := range minCoins { minCoins[i] = 6 } -> Option D

4. Quick Check:

   Slice length 6 and loop within range [OK]

Hint: Use make with length and loop with range for safe init [OK]

Common Mistakes:

• Creating slice with wrong length
• Looping beyond slice length causing runtime error
• Using literal slice with insufficient length

3. What is the output of the following Go code snippet?

coins := []int{1, 3, 4}
amount := 6
minCoins := make([]int, amount+1)
for i := 1; i <= amount; i++ {
    minCoins[i] = amount + 1
}
minCoins[0] = 0
for i := 1; i <= amount; i++ {
    for _, coin := range coins {
        if coin <= i && minCoins[i-coin]+1 < minCoins[i] {
            minCoins[i] = minCoins[i-coin] + 1
        }
    }
}
fmt.Println(minCoins[amount])

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Initialize minCoins array

   minCoins starts as [0,7,7,7,7,7,7] (7 = amount+1). We update minCoins for each amount from 1 to 6.

2. Step 2: Calculate minimum coins for amount 6

   Check coins 1,3,4 for each i:
   - i=1: minCoins[1]=minCoins[0]+1=1 (coin 1)
   - i=2: minCoins[2]=minCoins[1]+1=2 (coin 1)
   - i=3: minCoins[3]=minCoins[0]+1=1 (coin 3)
   - i=4: minCoins[4]=minCoins[0]+1=1 (coin 4)
   - i=5: minCoins[5]=minCoins[4]+1=2 (coin 1)
   - i=6: minCoins[6]=minCoins[3]+1=2 (coin 3)

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Minimum coins for 6 = 2 (e.g., 3+3) [OK]

Hint: Trace inner loop updates for each amount [OK]

Common Mistakes:

• Not updating minCoins correctly inside nested loops
• Confusing coin values with indices
• Forgetting to initialize minCoins[0] to 0

4. Find the error in this Go code for minimum coin change and select the fix:

coins := []int{1, 2, 5}
amount := 11
minCoins := make([]int, amount+1)
for i := 1; i <= amount; i++ {
    minCoins[i] = amount
}
minCoins[0] = 0
for i := 1; i <= amount; i++ {
    for _, coin := range coins {
        if coin < i && minCoins[i-coin]+1 < minCoins[i] {
            minCoins[i] = minCoins[i-coin] + 1
        }
    }
}
fmt.Println(minCoins[amount])

medium

A. Change 'coin < i' to 'coin <= i' in the if condition

B. Initialize minCoins with zeros instead of amount

C. Set minCoins[0] = amount instead of 0

D. Change outer loop to 'for i := 0; i < amount; i++'

Solution

1. Step 1: Identify the condition error

   The condition 'coin < i' skips cases where coin equals i, missing exact matches (e.g., coin=5, i=5).

2. Step 2: Correct the condition

   Changing to 'coin <= i' includes exact matches, allowing minCoins[i] to update correctly.

3. Final Answer:

   Change 'coin < i' to 'coin <= i' in the if condition -> Option A

4. Quick Check:

   Include coin equal to amount index [OK]

Hint: Use <= to include exact coin matches [OK]

Common Mistakes:

• Using < instead of <= causing missed updates
• Wrong initialization of minCoins array
• Incorrect loop ranges causing index errors

5. Given coins = [1, 5, 10, 25] and amount = 30, what is the minimum number of coins needed to make 30 using the coin change minimum coins algorithm?

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Analyze coin denominations and amount

   Coins are 1, 5, 10, 25. Amount is 30.

2. Step 2: Find minimum coins to make 30

   Use one 25 coin + one 5 coin = 2 coins total. Using smaller coins would require more coins.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   25 + 5 = 30 with 2 coins [OK]

Hint: Use largest coins first to minimize count [OK]

Common Mistakes:

• Assuming only 1-coin denominations
• Not considering combinations with larger coins
• Counting coins incorrectly