Optimized 2ms Java recursive solution, beats 99.95%, O(1) memory.


  • 2
    J

    This solution is an optimized version based on qgambit2's solution https://leetcode.com/discuss/76307/java-recursive-solution-3ms.

    public class Solution {
     	int minCount = Integer.MAX_VALUE;
    
    	public int coinChange(int[] coins, int amount) {
    		Arrays.sort(coins);
    		count(amount, coins.length - 1, coins, 0);
    		return minCount == Integer.MAX_VALUE ? -1 : minCount;
    	}
    
    	void count(int amount, int index, int[] coins, int count) {
    		if(amount % coins[index] == 0) {
    			int newCount = count + amount / coins[index];
    			if(newCount < minCount)
    				minCount = newCount;
    			//return;  // Not sure why return here will slow down in OJ. It's better in my local test however.
    		}
    		
    		if(index == 0)
    			return;
    			
    		for (int i = amount / coins[index]; i >= 0; i--) {
    			int newAmount = amount - i * coins[index];
    			int newCount = count + i;
    			
    			int nextCoin = coins[index-1];
    			if(newCount + (newAmount + nextCoin -1) / nextCoin >= minCount)
    				break;
    			
    			count(newAmount, index - 1, coins, newCount);
    		}
    	}
    }
    

    It's a recursive version, but instead of taking out one coin in each level of the recursion , this solution will take care of one kind of coins in each recursion level, so the the maximum depth of the recursion will be coins.length, it's very shallow DSF. So no matter how big the amount is, it won't cause stack overflow.

    For this particular solution, DP is not an ideal solution as it's not necessary to evaluate for all the previous amounts. Actually a very small portion of them is necessary.

    The important optimization for this solution is to determine earliest time to stop the loop when we are sure no valid solutions are possible in further iteration.

    if(newCount + (newAmount + nextCoin -1) / nextCoin >= minCount)
           break;
    

    This solution can run test case with extremely huge amount in less than 1ms without additional memory usage and stack overflow problem. For example: int[] coins = {7, 39, 83, 109, 901}; int amount = 1000000000;


  • 0
    M

    @jianwu What does the last if-statement mean in your code?
    At a higher level, I understand that this would mean that further recursion is worthless, but I do not understand what the statement inside the "if" signify. Could you explain it a bit?


  • 0
    D

    @mishrasonu1993
    I was trying to figure out too.
    This also works if you replace the if statement with

    if(newCount + newAmount/nextCoin >= minCount)
    break;

    As the least value that we can get by proceeding further is newCount + newAmount/nextCoin and if minCount is less than or equal to this value, it is safe to break.


  • 0
    R

    @Deepti @mishrasonu1993
    I just figured out:

    if(newCount + newAmount/nextCoin >= minCount)
    

    This statement is relaxed because it is a floor operation, meaning:
    "If it's floor is bigger than that, so any value higher than the floor will also be bigger than that".

    if(newCount + (newAmount + nextCoin - 1 ) / nextCoin >= minCount) break;
    

    This statement is more stringent though hard to understand:

    1. If newAmount is dividable by nextCoin, it is the same as newAmount/nextCoin because it is floor operation.
    2. If new Amount is not dividable by nextCoin, at least there will be newAmount/nextCoin+1 coins, so (newAmount + nextCoin - 1 ) / nextCoin also can achieve this!

    So smart of thinking of this expression!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.