Coin Change

• Difficulty: Medium
• Topics: Array, Dynamic Programming, Breadth-First Search
• Link: https://leetcode.com/problems/coin-change/

Problem Description

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Solution

1. Problem Deconstruction

Technical Restatement
Given an array coins of distinct positive integers representing coin denominations and an integer amount, compute the minimum cardinality of any subset-sum (with repetition allowed) of coins that equals amount. Return -1 if no such combination exists.

Beginner-Friendly Explanation
Imagine you have coins of different values (like 1¢, 5¢, etc.), and you need to make exact change for a certain amount using the fewest coins possible. You can use as many of each coin as you want. If it’s impossible, say so.

Mathematical Formulation
Let $C = \{c_1, c_2, ..., c_n\}$ be the set of coin denominations. Find the minimal $k$ such that:

$$\exists \,\, x_1, x_2, ..., x_n \in \mathbb{N} \quad \text{where} \quad \sum_{i=1}^n x_i = k \quad \text{and} \quad \sum_{i=1}^n x_i c_i = \text{amount}$$

If no such $(x_i)$ exists, return $-1$.

Constraint Analysis

1. Coins array length ≤ 12: Limits brute-force permutations but manageable for DP with O(amount) time.
2. Coin values up to $2^{31}-1$: Large coins can be ignored if they exceed the remaining amount during iteration.
3. Amount ≤ 1e4: DP approaches with O(amount) space are feasible (≈40KB for 1e4 integers).
4. Edge Cases:
   • amount = 0 → Return 0 (Example 3).
   • All coins > amount → Return -1 (Example 2).
   • Coins include 1 → Always solvable, but must compute minimal.

---

2. Intuition Scaffolding

Analogies

1. Real-World: Like a cashier minimizing coins given back as change.
2. Gaming: Collecting the fewest power-ups (of varying strengths) to reach a boss’s health bar.
3. Math: Shortest path in a graph where nodes represent amounts and edges represent coin usage.

Common Pitfalls

1. Greedy Fallacy: Assuming largest coins always yield minimal count (fails for non-canonical systems, e.g., coins [1,3,4], amount 6).
2. Ignoring Zero: Forgetting amount=0 requires explicit handling.
3. Unbounded Recursion: Attempting brute-force DFS without memoization leads to stack overflow.
4. Overcounting: Not tracking visited states in BFS, causing redundant work.
5. Space Inefficiency: Using 2D DP tables when 1D suffices.

---

3. Approach Encyclopedia

Brute Force (Recursive DFS)

• Idea: Exhaustively try all coin combinations.
• Pseudocode:

  def coinChange(coins, amount):
      def dfs(remaining):
          if remaining < 0: return -1
          if remaining == 0: return 0
          min_coins = float('inf')
          for coin in coins:
              res = dfs(remaining - coin)
              if res != -1:
                  min_coins = min(min_coins, res + 1)
          return min_coins if min_coins != float('inf') else -1
      return dfs(amount)
  

• Complexity: Time $O(S^n)$ (exponential), Space $O(S)$ (call stack).

BFS with Memoization

• Idea: Track amounts level-by-level, stopping at the first hit.
• Visualization:

  Amount: 11 → Children: 10 (1), 9 (2), 6 (5)
  Level 1: 10,9,6 → Level 2: 9,8,5; 8,7,4; 5,4,1 → ...
  

• Complexity: Time $O(S \cdot n)$, Space $O(S)$.

Dynamic Programming

• Idea: Tabulate minimum coins for all amounts from 0 to amount.
• Recurrence:

  $$dp[i] = \min_{\substack{c \in C \\ c \leq i}} (dp[i - c] + 1)$$

• Pseudocode:

  def coinChange(coins, amount):
      dp = [float('inf')] * (amount + 1)
      dp[0] = 0
      for i in range(1, amount + 1):
          for c in coins:
              if c <= i:
                  dp[i] = min(dp[i], dp[i - c] + 1)
      return dp[amount] if dp[amount] != float('inf') else -1
  

• Complexity: Time $O(S \cdot n)$, Space $O(S)$.

---

4. Code Deep Dive

Optimal Solution (Dynamic Programming)

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)  # Initialize to "impossible" state
    dp[0] = 0  # Base case: 0 coins needed for amount 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:  # Coin can contribute to amount i
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Line-by-Line Explanation

1. Line 2: dp array tracks minimal coins for each sub-amount.
2. Line 3: Base case requires 0 coins for amount 0.
3. Line 4: Iterate through all sub-amounts up to target.
4. Line 5-6: For each coin, if it can be used (≤ current amount), update dp[i] by considering using c.

Edge Case Handling

• Example 3 (amount=0): Directly returns dp[0] = 0.
• Example 2 (coins=[2], amount=3): dp[3] remains inf → returns -1.

---

5. Complexity War Room

Hardware Considerations

• For amount=1e4, dp uses ~40KB (4 bytes/int × 1e4), fitting in CPU cache.
• Iterating 1e4 × 12 = 1.2e5 operations → negligible on modern hardware.

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(S^n)	O(S)	5/10	❌
BFS	O(S⋅n)	O(S)	7/10	✅
DP	O(S⋅n)	O(S)	9/10	✅ Optimal

---

6. Pro Mode Extras

Variants

• Limited Coins: Each coin can be used once (knapsack problem).
• Number of Ways: Instead of minimal count, compute total combinations (LC 518).

Interview Cheat Sheet

• Key Insight: DP is optimal for this problem.
• Mention First: “This is a classic unbounded knapsack problem.”
• Test Cases: Always check amount=0 and coins larger than amount.