View on NeetCode
View on LeetCode

Problem

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] <= 2^31 - 1
• 0 <= amount <= 10^4

Solution

Approach 1: Dynamic Programming (Bottom-Up)

The key insight is to build up solutions for smaller amounts and use them to solve larger amounts. For each amount, try all coins and take the minimum.

Implementation

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for a in range(1, amount + 1):
            for coin in coins:
                if a >= coin:
                    dp[a] = min(dp[a], dp[a - coin] + 1)

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

Approach 2: BFS (Level-Order)

from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0

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

        while queue:
            curr_amount, num_coins = queue.popleft()

            for coin in coins:
                next_amount = curr_amount + coin

                if next_amount == amount:
                    return num_coins + 1

                if next_amount < amount and next_amount not in visited:
                    visited.add(next_amount)
                    queue.append((next_amount, num_coins + 1))

        return -1

Approach 3: Recursion with Memoization (Top-Down)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        memo = {}

        def dp(remaining):
            if remaining == 0:
                return 0
            if remaining < 0:
                return float('inf')
            if remaining in memo:
                return memo[remaining]

            min_coins = float('inf')
            for coin in coins:
                min_coins = min(min_coins, dp(remaining - coin) + 1)

            memo[remaining] = min_coins
            return min_coins

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

Complexity Analysis

Bottom-Up DP:

• Time Complexity: O(amount * n), where n is number of coins. For each amount, we try all coins.
• Space Complexity: O(amount) for the dp array.

BFS:

• Time Complexity: O(amount * n), similar to DP.
• Space Complexity: O(amount) for the queue and visited set.

Top-Down DP:

• Time Complexity: O(amount * n).
• Space Complexity: O(amount) for memoization and recursion stack.

Key Insights

1. Optimal Substructure: The minimum coins for amount a is 1 + minimum coins for (a - coin) across all coins.

2. Recurrence Relation: dp[a] = min(dp[a - coin] + 1) for all coins where coin ≤ a.

3. Base Case: dp[0] = 0 (zero coins needed for amount 0).

4. Greedy Doesn’t Work: We can’t just use largest coins first. For coins [1,3,4] and amount 6, greedy gives 4+1+1=3 coins, but optimal is 3+3=2 coins.

5. BFS Alternative: Treats this as a shortest path problem where each coin is an edge with weight 1.

6. Unbounded Knapsack: This is a variant of the unbounded knapsack problem with infinite supply of each coin.