Coin Change - Flipkart Interview Question & Solution

Coin Change

Flipkart

Array

Dynamic Programming

A vending machine has to give change using as few coins as possible. The available coin values are given as an array coins, and the machine has an unlimited supply of each. Given the change due, amount, return the smallest number of coins that add up to it exactly. If no combination works, return -1.

Examples:

Input: coins = [1, 3, 4], amount = 6
Output: 2
Why: 3 + 3 = 6. Always grabbing the biggest coin first gives 4 + 1 + 1, which uses three coins, so a greedy approach fails here.

Input: coins = [5, 10], amount = 3
Output: -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];
}