Hey guyzzz...👋🏻

This post is w.r.t 🪙 Coin change problem on Leetcode. Please have a look at description before jumping in...

The thing is, I knew that dynamic programming will be involved, because I was in a discussion about this with some colleagues at work💼. So now I knew I needed a recursive function.... And so I devised this formula👨‍🏫,

C(X) = min(C(X-x_i))+1, x_i ϵ {coins} X=amount X != 0
     = 0, X == 0

Brute force solution💪🏻

This was easily implemented.

java
public class Solution {

  public int coinChange(int[] coins, int amount) {
    if (amount < 1) return 0;
    return coinChangeUtil(coins, amount);
  }

  private int coinChangeUtil(int[] coins, int amount) {
    if (amount < 0) return -1;
    if (amount == 0) return 0;
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
      int res = coinChangeUtil(coins, amount - coin);
      if (res >= 0 && res < min) min = 1 + res;
    }
    return min;
  }
}

Time and memory required for this solution is exponential....duh.

Finding overlapping subproblems within the recursive function

However when I drew the recursion tree for [1,2,5] and 11 as inputs👆🏻 from formula(or the code) I observed that many sub-problems are needed to be solved repeatedly. So, overlapping subproblems are present within the recusive solution.

There's an observation to help us out in memoization. The only function parameter changing in this case is the amount. So, we possibly can store the minimum number of coins required to pay the amount for each possible amount value.

Thus, the recursive function becomes,

java
public class Solution {

  public int coinChange(int[] coins, int amount) {
    if (amount < 1) return 0;
    return coinChangeUtil(coins, amount, new int[amount+1]); // 35 ms
  }

  private int coinChangeUtil(int[] coins, int amount, int minCoins[]) {
    if (amount < 0) return -1;
    if (amount==0 || minCoins[amount] != 0) return minCoins[amount];
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
      int res = coinChangeUtil(coins, amount - coin, minCoins);
      if (res >= 0 && (1+res) < min) min = 1 + res;
    }
    minCoins[amount] = min==Integer.MAX_VALUE?-1:min;
    return minCoins[amount];
  }
}

Time complexity for this is O(k*n) and memory complexity is O(k), k being the amount, and n being the number of coin denominations.

Bottom-up approach

Personally speaking, it is easier for me to build the top down approach before the bottom up approach. But while practicing I make sure to give an attempt in building the bottom up approach.

The recursive logic is effectively the same, the only difference is we move from 0 to amount. Looking at the code will be much more easier to understand.

java
class Solution {
    public int coinChange(int[] coins, int amount) {
        int minCoins[] = new int[amount+1];
        Arrays.fill(minCoins, Integer.MAX_VALUE-1);
        minCoins[0] = 0;
        for(int i=1; i<=amount; i++){
            for(int coin: coins){
                if(i<coin) continue;
                minCoins[i] = Integer.min(minCoins[i-coin]+1, minCoins[i]);
            }
        }
        return minCoins[amount]==(Integer.MAX_VALUE-1)? -1: minCoins[amount]; // 13ms
    }
}

Time and memory complexity is same as for top down approach.

Optimisation on the Bottom-up approach

Well the above two approaches had near 20th percentile and 80th percentile respectively. As you already are aware, for me <90% isn't enough.

Well a simple thought spawned in my head🤔. Why not invert these two loops. I can minimise the invocations for amount loop that way and can also avoid one conditional check as well.

But I didn't take action on the idea (didn't even perform the dry run for it). Only after visiting the discussions platform and going through those posts did I implement it. I should have atleast performed the dry run for it.😕️.

Anyways, this change pushed the performance to over 90th percentile📈.

java
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] minCoins = new int[amount + 1];
        Arrays.fill(minCoins, Integer.MAX_VALUE - 1);
        minCoins[0] = 0;
        for(int coin:coins){
            for(int i = coin; i <= amount; i++){
                minCoins[i] = Math.min(minCoins[i - coin] + 1, minCoins[i]);
            }
        }
        return minCoins[amount] == Integer.MAX_VALUE? -1: minCoins[amount]; // 8ms
    }
}

Cheers guys. Be awesome 🎵.