We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Coin Change

Difficulty: Medium

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.

Key Insights

  • This is a classic dynamic programming problem where we need to find combinations of coins to achieve a specific amount.
  • We can build a solution using a bottom-up dynamic programming approach, where we calculate the minimum coins needed for all amounts up to the target amount.
  • The problem can also be approached using breadth-first search (BFS) to explore different combinations of coins.

Space and Time Complexity

Time Complexity: O(n * amount), where n is the number of different coin denominations.
Space Complexity: O(amount), for storing the minimum coins required for each amount.

Solution

The problem can be solved using dynamic programming by maintaining an array dp where dp[i] represents the minimum number of coins needed to make amount i. We initialize this array with a value greater than any possible number of coins (like amount + 1), except for dp[0], which is set to 0 (since no coins are needed to make the amount 0). For each coin, we iterate through the dp array and update the minimum coins needed for each amount.

Code Solutions

def coinChange(coins, amount):
    # Initialize dp array with amount + 1 (a value greater than any possible coin count)
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins are needed to make amount 0

    # Iterate over each coin
    for coin in coins:
        # Update dp array for all amounts that can include this coin
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    # If dp[amount] is still amount + 1, that means we cannot form that amount
    return dp[amount] if dp[amount] != amount + 1 else -1
← Back to All Questions