LeetCode 322: Coin Change Solution in Python – A Step-by-Step Guide

What Is LeetCode 322: Coin Change?

In LeetCode 322: Coin Change, you’re given an array of coin denominations coins and an integer amount. Your task is to find the minimum number of coins needed to make up that amount. If it’s impossible, return -1. For example, with coins = [1,2,5] and amount = 11, the minimum is 3 (5+5+1). This problem tests your ability to solve a classic unbounded knapsack problem, connecting to concepts in LeetCode 518: Coin Change II.

Problem Statement

• Input: An integer array coins (denominations) and an integer amount.
• Output: An integer—the fewest coins needed, or -1 if impossible.
• Rules:
• Use any coin denomination any number of times.
• Amount must be exact.
• Coins are positive integers.

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2³¹ - 1
• 0 <= amount <= 10⁴

Examples

• Input: coins = [1,2,5], amount = 11
• Output: 3 (5+5+1)
• Input: coins = [2], amount = 3
• Output: -1 (No combination works)
• Input: coins = [1], amount = 0
• Output: 0 (No coins needed)

Understanding the Problem: Minimizing Coins

To solve LeetCode 322: Coin Change in Python, we need to find the smallest number of coins from coins that sum to amount, or determine it’s impossible. A naive approach—trying all combinations recursively—is O(2^n), where n is the amount divided by the smallest coin, far too slow. Instead, we’ll use:

• Best Solution (Bottom-Up DP): O(amount * len(coins)) time, O(amount) space—fast and practical.
• Alternative Solution (Top-Down DP): O(amount * len(coins)) time, O(amount) space—intuitive but recursive.

Let’s start with the bottom-up DP solution, explained in a beginner-friendly way.

Best Solution: Bottom-Up Dynamic Programming

Why This Is the Best Solution

The bottom-up DP approach is the top choice for LeetCode 322 because it’s efficient—O(amount * len(coins)) time, O(amount) space—and builds the solution iteratively, avoiding recursion overhead. It computes the minimum coins for every sub-amount up to amount, using a simple array. It’s like counting change step-by-step—straightforward and quick!

How It Works

Think of this as filling a coin-count ladder:

• Step 1: Initialize DP Array:
• dp[i] = min coins to make amount i.
• Base case: dp[0] = 0, others = infinity.
• Step 2: Build Up:
• For each amount from 1 to amount:
• Try each coin; update dp[i] if using that coin reduces the count.
• Step 3: Result:
• dp[amount] is the answer, or -1 if still infinity.
• Step 4: Why It Works:
• Subproblems overlap (e.g., dp[5] reused in dp[6]).
• Bottom-up ensures all dependencies are ready.

It’s like climbing to the amount with the fewest steps!

Step-by-Step Example

Example: coins = [1,2,5], amount = 11

• Init: dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
• Amount 1: dp[1] = min(inf, 1+dp[0]) = 1
• Amount 2: dp[2] = min(inf, 1+dp[1], 2+dp[0]) = 1
• Amount 5: dp[5] = min(inf, 1+dp[4], 2+dp[3], 5+dp[0]) = 1
• Amount 10: dp[10] = min(inf, 1+dp[9], 2+dp[8], 5+dp[5]) = 2
• Amount 11: dp[11] = min(inf, 1+dp[10], 2+dp[9], 5+dp[6]) = 3
• Result: dp[11] = 3

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Initialize DP array with infinity
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0  # Base case: no coins for 0

        # Fill DP array
        for i in range(1, amount + 1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i], 1 + dp[i - coin])

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

• Lines 3-4: Set up dp array, base case dp[0] = 0.
• Lines 7-10: Iterate over amounts and coins:
• Update dp[i] if coin fits, using 1 + dp[remaining].
• Line 12: Return dp[amount] or -1 if impossible.
• Time Complexity: O(amount * len(coins))—two nested loops.
• Space Complexity: O(amount)—dp array.

This is like a coin-counting machine—steady and swift!

Alternative Solution: Top-Down DP with Memoization

Why an Alternative Approach?

The top-down DP approach—O(amount * len(coins)) time, O(amount) space—uses recursion with memoization to compute the same result, exploring from the target amount down. It’s more intuitive for some, showing the decision tree, though it has recursion overhead. It’s like asking “how few coins?” at every step—clear and recursive!

How It Works

Recurse with memory:

• Step 1: Define recursive function with memo:
• Base case: amount = 0 → 0.
• Try each coin, take min of subproblems.
• Step 2: Memoize to avoid recomputation.
• Step 3: Return result or -1.

Step-by-Step Example

Example: coins = [1,2], amount = 3

• Call(3):
• 1+Call(2): 1+1+Call(1): 1+1+1+Call(0) = 3
• 2+Call(1): 1+1+Call(0) = 2
• Memo: {0:0, 1:1, 2:2, 3:2}
• Result: 2

Code for Top-Down Approach

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

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

            min_coins = float('inf')
            for coin in coins:
                min_coins = min(min_coins, 1 + dp(amt - coin))
            memo[amt] = min_coins
            return min_coins

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

• Time Complexity: O(amount * len(coins))—memoized subproblems.
• Space Complexity: O(amount)—memo dictionary.

It’s a recursive coin explorer—thoughtful and thorough!

Comparing the Two Solutions

• Bottom-Up DP (Best):
• Pros: O(amount * len(coins)) time, O(amount) space, no recursion.
• Cons: Less intuitive initially.
• Top-Down DP (Alternative):
• Pros: O(amount * len(coins)) time, O(amount) space, clear recursion.
• Cons: Recursion overhead.

Bottom-up wins for performance.

Additional Examples and Edge Cases

• [1,3], 2: 2.
• [2,4], 7: -1.
• [], 5: -1.

Both handle these well.

Complexity Breakdown

• Bottom-Up DP: Time O(amount * len(coins)), Space O(amount).
• Top-Down DP: Time O(amount * len(coins)), Space O(amount).

Bottom-up is slightly leaner.

Key Takeaways

• Bottom-Up DP: Build up—efficient!
• Top-Down DP: Drill down—intuitive!
• Python: Arrays and recursion shine—see [Python Basics](/python/basics).
• Change: Coins teach optimization.

Final Thoughts: Count Your Coins

LeetCode 322: Coin Change in Python is a dynamic programming classic. The bottom-up solution offers speed and simplicity, while top-down provides a recursive lens. Want more DP challenges? Try LeetCode 518: Coin Change II or LeetCode 300: Longest Increasing Subsequence. Ready to make change? Head to Solve LeetCode 322 on LeetCode and minimize those coins today!