Skip to content

LC 322. Coin Change (Medium)

mccornet edited this page Jul 28, 2021 · 9 revisions

322. Coin Change

Challenge

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.

Solutions

There are 3 solutions to this problem discussed in this page.

  1. Recursive
  2. Bottom up using tabulation
  3. Bottom up using BFS

Recursive Solution

The first solution to gain insight is the recursive solution. But even with memoization that runs too slow.

from functools import lru_cache


class Solution:

    def coinChange(self, coins: list[int], amount: int) -> int:

        @lru_cache()
        def top_down_recursion(amount):
            # Edge cases
            if not amount: return 0             # done
            if amount < 0: return float('inf')  # punish negative payments
            
            optimal_result = float('inf')

            for coin in coins:
                partial_result = top_down_recursion(amount - coin)
                candidate = partial_result + 1  # used one extra coin
                optimal_result = min(optimal_result, candidate)

            return optimal_result
   
        result = top_down_recursion(amount)
        
        if result == 0: return -1  # indicates payment not possible
        return result

Bottom-up using tabulation

A good explanation is found on www.codeproject.com

Starting at the base-case (0) all coins are tried. Impossible values are ignored, and from the values already calculated take the minimum value and add one for the extra coin used. This uses more space than the BFS approach since we have to allocate an array, but is faster in this particular example. See also Leetcode 70. Climbing Stairs

JavaScript

Runtime: 104 ms, faster than 95.41%

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {

    let max = amount+1;
    let dp_cache = new Array(amount+1, max);
    // base case
    dp_cache[0] = 0;
    
    for(let change = 1; change <= amount; change++) 
    {
        let min_coins = max;
        
        for(const coin of coins)
        {
            let prev_change = change - coin;
            
            if(prev_change < 0) continue;
            
            if(dp_cache[prev_change] + 1 < min_coins)
            {
                min_coins = dp_cache[prev_change] +1;
            }            
        }
        dp_cache[change] = min_coins;
    }
    if(dp_cache[amount] === max) return -1;
    return dp_cache[amount];
};

C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        
        // create a cache for the bottom up approach.
        // Zero indexed, and the base case is zero
        // So the length of the cache is amount + 1
        int Max = INT_MAX-1;
        vector<int> dp_cache(amount + 1, Max);
        
        // set the base case
        dp_cache[0] = 0;
        
        // the base case is zero, so we start all next cases at 1
        // till we reach the desired amount
        for(int change=1; change <= amount; change++)
        {
            int min_coins = Max;
            
            for(int coin : coins)
            {
                // going bottom up by trying to find pre calculated values
                int prev_change = change - coin;
                
                // skip negative payments
                if (prev_change < 0) continue;
                
                // update the minimum count when applicable
                if (dp_cache[prev_change] + 1 < min_coins)
                {
                    min_coins = dp_cache[prev_change] + 1;
                }
            }
            
            // store the bottom-up result
            dp_cache[change] = min_coins;            
        }
        
        // return the result. if the result is still INT_MAX we did not solve the problem and return -1
        if(dp_cache[amount] == Max) return -1;
        
        return dp_cache[amount];
    }
};

Bottom-up approach using BFS

This BFS approach is based on the example given by Rossi. Because of the BFS the first path will be the shortest. It also ignores values that are already in the queue. For example, given coins [1, 2, 5]; on the second level 5 + 2 is ignored because 2 and 5 are already in the queue.

Python

Runtime: 624 ms, faster than 98.14%

class Solution:

    def coinChange(self, coins: list[int], amount: int) -> int:
        from collections import deque
        # Store Change, Search depth. 
        # Search depth is the number of coins
        # Provide an initial case for zero change
        coin_change_depth = {0: 0}

        # Build up a BFS queue of coin combinations
        # Start with zero paid (adding a node to tree)
        coin_combinations = deque([0])

        while coin_combinations:
            coin_change = coin_combinations.popleft()

            # BFS: the match was reached via the shortest path
            if coin_change == amount: 
                return coin_change_depth[amount]

            for coin in coins:
                next_payment = coin_change + coin

                # Skip overshoot payments 
                # End case in recursion
                if next_payment > amount: continue

                # Skip payments already made 
                # via a previous BFS coin change route
                if next_payment in coin_change_depth: continue

                # Add the current change and depth to the dict
                # And add this to the queue of payment possibilities
                coin_change_depth[next_payment] = coin_change_depth[coin_change] + 1
                coin_combinations.append(next_payment)

        return -1  # No combination could reach the result        

JavaScript

Runtime: 196 ms, faster than 30.77%

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {

    // store change and depth
    // the depth is the number of coins
    // initial case is zero change with zero coins
    let coin_change_depth = {0: 0}
    // BFS Queue
    let bfs_coin_queue = [0]

    while (bfs_coin_queue.length) {
        let coin_change = bfs_coin_queue.shift()

        // Reached amount via bfs, guaranteed least nr coins
        if (coin_change === amount) return coin_change_depth[amount]
        
        for (const coin of coins) {
            let next_payment = coin_change + coin
            
            // skip overshoot
            if (next_payment > amount) continue

            // skip payments already tried (part of BFS)
            if (next_payment in coin_change_depth) continue

            // append the dict and queue
            coin_change_depth[next_payment] = coin_change_depth[coin_change] + 1
            bfs_coin_queue.push(next_payment)
        }
    }
    return -1
};

Clone this wiki locally