Would be cool if after you coded the solution you can loop through the program with illustration. For example incrementing variables and drawing out what arrays look like, how they change when we go through loops, etc. It would be helpful since not everyone codes in Java and it makes it easier to understand. Not having to figure out what does "Arrays.fill(dp, amount + 1)" look like: Does it look like [11], does it look like [11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11]? So just some syntax things in other languages that slow learning down could be fixed.
i was also trying to figure that out ,Arrays.fill(dp, amount + 1) will populate the array with max val (i.e amount+1) , cuz even the smallest denomination (1) need "amount" no. of coins i.e
Would be nice to see some solution in C++ too. Also something like breaking down video into: Understanding Problem, Sudo code, Discussing different solution and which one most efficient ( some what like most white board interviews will be like ) and then diving into coding part. Also a video for beginners to get a walk through Leetcode and such platform. Because for some who recently just learnt coding,Algo and Data structure, it can be difficult to understand how to even understand the example, output, input etc. Thanks
question .........1)put coins in a max heap 2)curr=pull out the head of heap(max coin) to_ret=0 3)Find n where n*curr is greatest multiple of curr smaller than amount 4)to_ret +=n 5) repeat steps 2 to 4 till heap is empty 6)return to_ret why cant we do this?
Hi Kevin!All your videos are straight right to the point and solutions are easy to understand.Thanks much.Would you do a solution video for Word Ladder ll problem in Leetcode?
It would have taken more than 1 hour if I didn't refer to your explanation. You have explained it so well, it took only 15 minutes. Thanks a lot, @Kevin Naughton Jr. Love from India
You could loop trough the coins as outer for and avoid to check i is less than the value: for (const auto& coin: coins) for (int i =coin ; i < amount+1; ++i) dp[i]=min(dp[i], 1 + dp[i - coin]);
The new easy and intuitive way i found with nearly O(n) time complexity is 1) First sort array in O(nlogn) using merge sort 2) Fewer coins will be used, if coin value is high. So come from back and then decrease one by one element in array..max O(n)
Can you explain line 9 a little more? Isn't it possible that dp[i - coins[j]] produces a negative index? Also, dp[i] should just give us the answer for each i right? Why are we looking up the index in dp based on the value of a coin?
How do you identify if a problem needs dp? I'm a complete beginner to dp and I have trouble figuring out when the problem calls for it. Thanks for the video!
If your problem has subproblems (you have to solve smaller problems first in order to solve the larger problem), you can use DP. In general, if you think "hey, this problem can be solved with recursion," consider whether it can be solved with DP and memoization first.
How about this approach? Sorting the coins in the reverse order from the largest to the smallest and walking over the sorted array to do division and modulus operations.
That's a reasonable first intuition, but it won't work cause you won't necessarily use the largest coins. Imagine the following case: amount = 8, coins = [2,5]. it will return -1. where as it should return 4.
@@anisharbi3510 The modulus approach will work with your example, in that you will sort your available coins as [5, 2]: it will see that it needs zero of the 5 coins, and two of the 2 coins. The place where this approach fails is if you have coins of [10, 8, 1], and you need to get to 16, the modulus approach will first take a 10 coin, then zero 8's, and six 1's, whereas the correct approach would be to take two 8's.
Good explanation, but you should also mentioned why you picked (amount + 1) as your default invalid instead of say Integer.Max. Because it seems like Integer.Max works fine too? I don't see how it would overflow or such. Please correct me if this is incorrect.
I like your solutions but It would be nice as well if you could draw it out on the screen with the table and all. Hearing the solution verbally is hard for me to follow along.
If the interviewer allows a coin to be 0.5 cents, then the arrays.fill(dp, amount+1) would be wrong right? What is a good value to initialize it to then?
This is a great video to understand. If you keep it currency agnostic, it's better because people outside the US really get confused with examples of nickels and cents.
Thanks so much for your videos, Kevin! They're super helpful and I really enjoy watching them. I would love to chat with you about some interviews I have coming up in Microsoft.
I would like to know your top process to realize that it's more efficient to loop tru amount instead of making combinations of coins. i tried every BFS, DFS and dividing recursively but it timed out.
Ariel robles alvarez the cheeky way is to look at the given parameters of the problem. If we build up to amount and try all coins, we have coins*amount complexity. By contrast, pure recursion could have 2^n complexity since we are deciding each time whether or not we accept a coin. We need to take advantage of the fact that we know our amount and to shrink the goal of getting that amount until it equals the base case of a single coin
Super happy to find your channel. It helped me a lot man. Thanks for that. Is it possible for you to do word permutations and minimum sub sequence DP problems please?
great solution but don't we need to account for the fact if amount is less than any coin in coins? Surely that should return -1 but your code will lead to an error?
calfland79 because that is stored in an earlier index in the dp array. Example: you have coins {1, 5} and you want to make amount of 11. Of course, this will take 3 coins. At dp[11], on line 9, you’d have 1 + dp[11-5] = dp[6]. At dp[6], you have 1 + dp[1]==1 (so dp[6] == 2), so dp[11]==3. The two nickels were accounted for at dp[11] and dp[6]
Question regarding that optimization step, because you used Arrays.sort(), would you add the sort's time complexity to the final time complexity analysis? Why or why not?
I have a question. What stops me from just saying I want to iterate through the array and go backwards and just keep filling the maximum denomination everytime.
Hi Kevin! Thanks for your videos. But how does this work for [2] coins, and amount = 3 ? It will return min coins as 1, but it should be -1. Can you explain?
Hi Kevin! Thank you for the videos- they have been super helpful as I do interview prep. I became a patreon member recently and would love to get an invitation to your discord channel and perhaps setup a time to chat.
for int i = 0 makes no sense because you already solved that subproblem. You should start iterating at i = 1. BTW your videos are awesome. Thank you for all of them :D
so the dp array is essentially the least number of coins at that array so if amt = 2 then dp[2] would be minimum coins at that point. In our case, the 1+ dp[i - coins[j]] can be thought of as taking an extra coin so in the case of dp[3], you would be adding 1 + dp[3 - 2]
Thanks man. Using your idea I wrote this code. We can avoid sorting and if/else condition public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int c : coins) { for (int i = c; i amount ? -1 : dp[amount]; }
I think I figured out an even faster solution. Given that you have an infinite number of each coins, you don't need to work a tech job, hell you don't need to work at all. 0ms and 0mb, faster than 100%.
You're so good at solving leetcodes! Why don't you work for a FANG company since you can obviously pass their interviews, is it because you prefer working at a smaller company?
thanks! If you like my explanations be sure to join the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining a premium plan if you can!
Kevin, This is my C++ implementation. Any comment? Thanks int CointChange(std::vector& coins, int amount) { std::sort(coins.begin(), coins.end(), std::greater()); for (auto a : coins) { if (amount % a) return amount / a; if (std::find(coins.begin(), coins.end(), (amount % a)) != coins.end()) return (amount / a) + 1; } return -1; }
@Josh Ribakoff greedy doesn't work certain when certain coin denominations applied against certain amounts so it's an unreliable approach. Also, by tabulating the previous results into an array the presented solution is indeed DP. DP is either recursion + memoization, or, tabulation, and he used the later. Cheers.
