algoadvance

Leetcode 518. Coin Change II

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Compute the number of ways to make up that amount using the given coins. You may assume that you have an infinite number of each kind of coin.

Clarifying Questions

1. Can the amount be zero?
   • Yes, if the amount is zero, there is exactly one way to make up the amount (using no coins).
2. Can the array of coins be empty?
   • Yes, if the array is empty, the only way we can make an amount of zero is by using no coins. For any other amount, it is impossible, so the result is zero.
3. Are coin values always positive?
   • Yes, we assume all coin denominations are positive integers.

Strategy

We can solve this problem using Dynamic Programming (DP). The idea is similar to the knapsack problem.

1. Define the DP array:
   • Let dp[i] denote the number of ways to make up the amount i using the given coins.
2. Initialize the DP array:
   • dp[0] = 1, because there is one way to make amount 0, which is to use no coins.
3. Fill the DP array:
   • For each coin in coins array, update the dp array by iterating through amounts from the coin’s value up to the desired amount.
4. Transition relation:
   • For every coin value coin, update the dp array as follows:

     for (int i = coin; i <= amount; i++) {
         dp[i] += dp[i - coin];
     }
     

Code

Here’s a Java implementation of the described strategy:

public class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // base case: one way to make amount 0

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin]; 
            }
        }

        return dp[amount];
    }
}

Time Complexity

• Time Complexity: O(n * m), where n is the number of coins and m is the amount. This is because we iterate through each coin and for each coin, we update the dp array from the coin’s value up to the amount.
• Space Complexity: O(m), where m is the amount, for storing the dp array.

This approach ensures that we efficiently calculate the number of ways to make up the given amount using the provided coins.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?