LeetCode Solution 322 - Coin Change Problem

 Problem Statement

Given an array coins representing different denominations of coins and an integer amount, return the fewest number of coins needed to make up that amount. If it is impossible to make the amount, return -1.

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

Optimal Approach - Dynamic Programming (Bottom-Up)

The best way to solve this problem efficiently is using Dynamic Programming (DP) with a bottom-up approach.

Explanation:

1. Create a dp array of size amount + 1, initialized to amount + 1 (an impossible high value) except dp[0] = 0.
2. Iterate over each coin in coins, updating dp[j] = min(dp[j], dp[j - coin] + 1) for every j from coin to amount.
3. If dp[amount] remains unchanged (amount + 1), return -1, else return dp[amount].

C++ Code (LeetCode-Compatible)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        
        for (int coin : coins) {
            for (int j = coin; j <= amount; ++j) {
                dp[j] = min(dp[j], dp[j - coin] + 1);
            }
        }
        
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

Step-by-Step Explanation

1. Initialization:

   • We create a dp array of size amount + 1 and set it to amount + 1 (a large number, as an impossible value).
   • dp[0] = 0 because 0 coins are needed to make an amount of 0.

2. Iterate Over Each Coin:

   • For each coin, iterate over all amounts j from coin to amount.
   • Update dp[j] by checking if using the current coin reduces the number of coins required.

3. Return Result:

   • If dp[amount] remains unchanged, return -1 (not possible to form the amount), otherwise return dp[amount].

Dry Run / Execution Steps

Example:

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

DP Table Calculation:

dp[0]  = 0  (Base case)
dp[1]  = 1  (1 coin of 1)
dp[2]  = 1  (1 coin of 2)
dp[3]  = 2  (1+2)
dp[4]  = 2  (2+2)
dp[5]  = 1  (1 coin of 5)
dp[6]  = 2  (1+5 or 2+2+2)
dp[7]  = 2  (2+5)
dp[8]  = 3  (3 coins of 2 or 1+2+5)
dp[9]  = 3  (2+2+5)
dp[10] = 2  (5+5)
dp[11] = 3  (1+5+5)

Output: 3

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	Exponential $O(2^n)$	O(n)	Slow for large inputs
Greedy Approach	Undefined (Fails in some cases)	O(1)	Doesn't work for cases like coins=[3,7] and amount=14
Dynamic Programming (Top-Down with Memoization)	O(n*amount)	O(n+amount)	Similar efficiency but requires extra recursion overhead

Best Solution & Why It’s Best

The bottom-up DP approach is the most efficient because:

1. It avoids recursion overhead.
2. It has a predictable time complexity of O(n*amount).
3. It guarantees the optimal solution.

Complexity Analysis

• Time Complexity: O(n * amount) (where n is the number of coins)
• Space Complexity: O(amount) (for storing dp array)

Conclusion

• The best approach is Bottom-Up Dynamic Programming.
• Alternative approaches like recursion or greedy fail in some cases.
• Recommended practice problems:
  • Minimum Coins to Make Change
  • Unbounded Knapsack Problem
  • Combination Sum (LeetCode 39)