algoadvance

Leetcode 322. Coin Change

Problem Statement

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

Clarifying Questions

  1. Negative Amount: Can amount be negative?
    • No, the amount is always non-negative.
  2. Empty Coins Array: Could the coins array be empty?
    • Yes, the array could be empty. In such cases, if the amount is greater than 0, the output should be -1.

Strategy

We’ll use dynamic programming to solve the problem. We’ll initialize an array dp where dp[i] represents the minimum number of coins needed to get the amount i. The size of the dp array will be amount + 1 (to include 0).

  1. Initialize dp[0] = 0 because 0 coins are needed to make the amount of 0.
  2. For all other amounts, initialize dp[i] = amount + 1 which signifies that initially, we assume it’s impossible to make that amount.
  3. Traverse from 1 to amount:
    • For each coin in the list, if the amount is greater than or equal to the coin value, update the minimum coins needed. This can be done using the formula: 
      dp[i] = std::min(dp[i], dp[i - coin] + 1);
  4. Finally, check the dp[amount]. If it’s still amount + 1, return -1 (impossible to form the amount), otherwise, return dp[amount].

Time Complexity

The time complexity of the solution is O(n * amount), where n is the number of different coins.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        if (coins.empty()) {
            return amount == 0 ? 0 : -1;
        }

        std::vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0; // Base case: It takes 0 coins to make amount 0

        for (int i = 1; i <= amount; ++i) {
            for (const int &coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = std::min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

This code first checks if the coins array is empty and handles that case accordingly. Then it initializes the dp array and fills it using a nested loop. Finally, it checks if it’s possible to form the required amount and returns the result.

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