How to Solve: Coin Change – Complete Guide for FAANG Interviews

How to Solve: Coin Change – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can handle dynamic programming, greedy algorithms, and edge cases under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Coin Change, ensure you understand: 1. Dynamic Programming (DP) – Memoization, tabulation, and state transitions. 2. Greedy Algorithms – When they work (and when they don’t). 3. Breadth-First Search (BFS) – For finding the shortest path (minimum coins).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeat this checklist for every Coin Change problem:

1. Clarify the Problem
2. Can coins be reused? (Unbounded vs. 0/1 Knapsack)
3. Do we need the minimum number of coins or all possible combinations?

4. Are there negative amounts? (No, but confirm.)

5. Choose the Right Approach

6. Minimum coins? → DP (Unbounded Knapsack) or BFS.
7. All combinations? → Backtracking or DP (count ways).

8. Greedy works? → Only for canonical systems (rare in interviews).

9. Define the DP State

10. dp[i] = minimum coins to make amount i.

11. dp[i][j] = minimum coins to make amount i using first j coins (if order matters).

12. Base Case

13. dp[0] = 0 (0 coins needed for amount 0).

14. dp[i] = ∞ (or a large number) for unreachable amounts.

15. State Transition

16. For each coin, update dp[i]:
    python
dp[i] = min(dp[i], dp[i - coin] + 1)

17. Optimize Space (If Possible)

18. Use a 1D array instead of 2D if order doesn’t matter.

19. Handle Edge Cases

20. Amount = 0 → return 0.

21. No solution → return -1 or None.

22. Test with Examples

23. Small cases (e.g., coins = [1,2,5], amount = 11 → 3 coins).
24. Edge cases (e.g., amount = 0, coins = []).

? WORKED EXAMPLES

Example 1 – Basic: Minimum Coins (LeetCode 322)

Problem: Given coins of different denominations and an amount, return the fewest number of coins needed. If impossible, return -1.

Framework Application: 1. Clarify: Coins can be reused (unbounded knapsack). 2. Approach: DP (Unbounded Knapsack). 3. DP State: dp[i] = min coins to make amount i. 4. Base Case: dp[0] = 0, dp[i] = ∞ for others. 5. Transition:
python
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1) 6. Edge Cases: amount = 0 → 0, no solution → -1.

Full Code (Python):

def coinChange(coins, amount):

    dp = [float('inf')]  (amount + 1)

    dp[0] = 0

    for coin in coins:

        for i in range(coin, amount + 1):

            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

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

Why This Works: - DP builds up solutions from smaller amounts. - Each dp[i] is the minimum of all possible coin choices.

Example 2 – Medium: All Possible Combinations (LeetCode 518)

Problem: Given coins and an amount, return the number of combinations that make up that amount. Coins can be reused.

Framework Application: 1. Clarify: Order doesn’t matter (e.g., [1,2] is same as [2,1]). 2. Approach: DP (count ways). 3. DP State: dp[i] = number of ways to make amount i. 4. Base Case: dp[0] = 1 (one way to make 0). 5. Transition:
python
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]

Full Code (Python):

def change(amount, coins):

    dp = [0]  (amount + 1)

    dp[0] = 1

    for coin in coins:

        for i in range(coin, amount + 1):

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

    return dp[amount]

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

Why This Works: - DP accumulates ways to form each amount. - Outer loop over coins ensures order doesn’t matter.

Example 3 – Hard/Follow-Up: Minimum Coins with BFS (Shortest Path)

Problem: Same as Example 1, but optimize for minimum coins using BFS.

Framework Application: 1. Clarify: BFS finds the shortest path (minimum coins). 2. Approach: Treat amounts as nodes, coins as edges. 3. Queue: Start with 0, explore 0 + coin for each coin. 4. Visited Set: Avoid reprocessing the same amount.

Full Code (Python):

from collections import deque

def coinChange(coins, amount):

    if amount == 0:

        return 0

    queue = deque([(0, 0)])  # (current_amount, num_coins)

    visited = set([0])

    while queue:

        current, steps = queue.popleft()

        for coin in coins:

            next_amount = current + coin

            if next_amount == amount:

                return steps + 1

            if next_amount < amount and next_amount not in visited:

                visited.add(next_amount)

                queue.append((next_amount, steps + 1))

    return -1

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

Why This Works: - BFS explores all possible amounts level by level (shortest path first). - Visited set prevents redundant work.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. For Coin Change, here’s your battle plan:

1. Clarify: Can coins be reused? Do we need min coins or all combinations?
2. Choose: DP for min coins, BFS for shortest path, backtracking for all combos.
3. DP Setup: dp[0] = 0, dp[i] = ∞ for others.
4. Transition: For each coin, update dp[i] = min(dp[i], dp[i - coin] + 1).
5. Edge Cases: Handle amount = 0 and no solution.
6. Optimize: Use 1D DP if order doesn’t matter.

Remember: Greedy only works for canonical coins—DP is your default. Test with small cases, and you’ll crush it. Good luck!

? Final Notes

• Practice Variations: Try "Coin Change II" (all combinations) and "Minimum Cost for Tickets" (DP with time windows).
• Whiteboard Tip: Draw the DP array and fill it step-by-step.
• Time Management: If stuck, start with brute force, then optimize.

Now go ace that interview! ?