Leetcode 322 - Coin Change

Table of contents

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

Explanation/Approach

The “Coin Change” problem is a classic example of dynamic programming. The idea is to build a solution iteratively while solving smaller sub-problems. We use an array dp where dp[i] will represent the minimum number of coins needed to make up the amount i.

Dynamic Programming Approach:

• Initialization: We initialize an array dp of size amount + 1 with a large value (like amount + 1) since the minimum number of coins needed can never exceed the amount.
• Base Case: dp[0] is set to 0 because no coins are needed to make up amount 0.
• Iteration: For each coin value in coins, we update the dp array. For every amount i from the value of the coin up to amount, we calculate dp[i] as the minimum of dp[i] and dp[i - coin] + 1. This represents the minimum number of coins needed to make the amount i, considering the current coin.
• Result: After filling the dp array, if dp[amount] is still greater than amount, it means it’s not possible to make up that amount with the given coins, so we return -1. Otherwise, we return dp[amount].

Solution: Dynamic Programming

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Initialize the dp array with amount + 1, which is an impossible high number of coins
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0  # Base case: No coins needed for amount 0

        # Iterate over each coin
        for coin in coins:
            # Update the dp array for each amount
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)

        # If the amount is not achievable, return -1
        return dp[amount] if dp[amount] != amount + 1 else -1

Time and Memory Complexity

The time complexity is O(n*m) where n is the amount and m is the number of coins, as we iterate over each coin for each amount up to amount. The space complexity is O(n) due to the additional array dp used for dynamic programming.

Explanation

The dynamic programming solution builds up the minimum number of coins needed for each amount up to the target amount. It iterates through each coin, updating the dp array to reflect the minimum coins needed for each amount. If the final amount can’t be achieved with the given coins, the function returns -1, indicating it’s not possible.

Visualization Process:

1. Initialize the DP Array:

   • We start with a dp array where dp[i] represents the minimum number of coins needed to make the amount i.
   • Initialize dp with a size of amount + 1 (12 in this case) and set all values to a large number (12 here) except for dp[0], which is set to 0.
   • Initial dp array: [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]

2. Process Coin 1:

   • For each amount from 1 to 11, we check if using a coin of 1 helps in reducing the number of coins.
   • Updated dp: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

3. Process Coin 2:

   • Start from amount 2. Check if using a 2-coin is better than the current number of coins in dp.
   • After processing coin 2: [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

4. Process Coin 5:

   • Start from amount 5. Check if using a 5-coin is better than the current number of coins in dp.
   • Final dp: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

Final Output:

• The value at dp[11] is 3, indicating the minimum number of coins needed to make 11 is 3.
• The coins used are two 5s and one 1.

Visual Representation:

Coin: 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Coin: 2
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

Coin: 5
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

Result: Minimum coins for amount 11 is 3 (5 + 5 + 1)

Each step in the array represents the dynamic updating of the minimum coins needed for each amount. This visual representation shows how the solution evolves with each coin denomination.