AlgoViz: Interactive Algorithm Visualization Tool

Back to All Questions

Coin Change

Flipkart

Array

Dynamic Programming

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:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Solution Walkthrough

This is a classic dynamic programming problem. We want to find the minimum number of coins for an amount, which can be broken down into subproblems: finding the minimum number of coins for smaller amounts.

Create a DP array, dp, of size amount + 1. Initialize all its values to a sentinel value that represents infinity (e.g., amount + 1), which indicates that the amount is not reachable yet. Set dp[0] = 0, because 0 coins are needed to make an amount of 0.
Iterate from 1 to amount. For each amount i, we will try to find the minimum number of coins.
Inside this loop, iterate through each coin in our coins array.
If a coin is less than or equal to the current amount i, it means we can potentially use this coin. The number of coins needed would be 1 + dp[i - coin] (1 for the current coin, plus the minimum coins needed for the remaining amount).
We update dp[i] to be the minimum of its current value and the value we just calculated: dp[i] = Math.min(dp[i], 1 + dp[i - coin]).
After the loops complete, dp[amount] will hold the minimum number of coins. If its value is still our sentinel value (infinity), it means the amount was not reachable, so we return -1. Otherwise, we return dp[amount].

The time complexity is O(amount * n) where n is the number of coins, because of the nested loops. The space complexity is O(amount) for the DP array.

function coinChange(coins, amount) {
    // Create a DP array to store the minimum number of coins for each amount.
    // Initialize with a value larger than any possible answer.
    const dp = new Array(amount + 1).fill(amount + 1);

    // Base case: 0 coins are needed to make an amount of 0.
    dp[0] = 0;

    // Iterate through all amounts from 1 to the target amount.
    for (let i = 1; i <= amount; i++) {
        // For each amount, iterate through all coin denominations.
        for (const coin of coins) {
            // If the coin value is less than or equal to the current amount...
            if (coin <= i) {
                // ...we can potentially use this coin.
                // The number of coins would be 1 (for this coin) + the minimum
                // coins needed for the remaining amount (i - coin).
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }

    // If dp[amount] is still our sentinel value, it means the amount
    // cannot be made up. Otherwise, it holds the minimum number of coins.
    return dp[amount] > amount ? -1 : dp[amount];
}