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?
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
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?
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]);
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.
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.
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?
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
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?
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.
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.
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?
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)
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.
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.
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]
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?
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
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.
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]
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.
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?
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?
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 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]; }
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!
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%.
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.
What question should I cover next?
Sir please try to cover questions related to binary trees👍
@@ismailelhabbash I'll add that to my list!
@@MohammedJavid-jz8vi You've got it Javid!
Can you do Word Squares and Sliding window maximum?
@@kuppurajkarthik I'll add it to my list! Do you have the problem numbers?
Instead of saying ' believe it or not it works", consider adding an explanation of why this works in more detail. Thank you for your videos 😊
I like how you are using a bottom-up approach to DP instead of recursion. It makes your code much cleaner and simple!
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.
you should pay him to do that. he is not your slave....
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
Your solutions always make it look so simple compared to Leetcode or GeeksforGeeks. Great work!!
Thanks Kuppuraj I'm happy to hear my explanations are helpful :)
His solutions are just copy-paste from solution tab on leetcode.
@@notwhoyouthink666 doesn't matter, he's explaining it in a matter that is digestible for Noobs like me
Ikrrrrrrrrrrrr....this gives me faith to keep working on my skills!!! Such a great teacher
@@notwhoyouthink666 u can also do the same, please try to appreciate someone's effort instead of negativity.
Great videos Kevin. Just a note on a very small optimization - Since you already calculated dp[0] = 0, you can loop from i = 1, instead of i = 0;
thanks John and yes nice catch!
Line 17, "dp[amount] > amount ? -1 : dp[amount]" does dp[amount] > amount comparable?
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
How come you make it look so easy? Genius.
Hi Kevin,
do you have a playlist of all your dynamic programming leetcode solutions?
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?
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
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?
What a dedication to teaching, almost losing breath! The video is much appreciated though! :)
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]);
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.
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!
As far as i know , DP is mainly used for optimisation problems(minimisation or maximising) .
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.
Sir, Your solutions are always very easy to understand compared to the other online resources.
Thanks for it.
Took me a while to understand but the solution is perfect. Thanks!
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?
i - coins[j] will never be negative, because there is a condition check (coin[j]
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
Thanks for a great video! Why we can't use greedy approach here?
Hi Kevin,
Can you please add Snake and Ladders problem. I know its an easy one, but like to see your approach. Thanks
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?
how do you come up with this, inspirational fr lmao
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.
One problem I always get when solving these is how do I get the subproblem. Thank you for this!
You good man..you good! Struggled with this guy for a lil
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.
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?
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)
this wudnt pass all test cases for this problem
Bottom up approach + optimization by removing obvious no-fits
Line 17, "dp[amount] > amount ? -1 : dp[amount]" does dp[amount] > amount comparable?
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.
This wouldn't work don't waste your time.
i tryied that approach, but it timed out.
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.
@@pjamestx The amount is 8 not 4 for the example anis gave.
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.
In line 9, why it is 1 + dp[i - coins[j]. In other words, how do you know only take 1 of coins[j], not 2, 3, or 4.
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]
@@iPoopDinosaurs Got it. Thanks.
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?
Thanks and I'll see what I can do!
first video of this problem that i actually understood ty
this is a FANTASTIC explanation!!! thank you so much!!!
anytime Alyssa and thanks!
I still didn't understand login on line number 9. Can someone explain deeper?
really i don't know what leetcode is but after watching this video i am addicted to it thank you so much
Thank you so much, these explanations are really great!
What a underrated channel?!!!
1. dp - is a bad name for array of number min coins for each value
2. first loop should start from 1 not 0 - this is redundant iteration
Love the explanation and the optimization tip in the end. Thanks for making the video.
can someone pls explain line # 9, I still didn't get it
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
I was also thinking the same
I don't get it Amazon boy. please help
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.
{1,3,4,5} and sum=7. do it yourself!!!
Why do we have to have the "+1" at dp[i] = Min(dp[i], 1 + dp[i-coins[j]]
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]
because we are taking "1" coin of value: coin[j].
This dude is gold
ammm no.... why wont you sort the array in descending order and for each i do amount/arr[i] = a and amount MOD arr[i] = b and so on... Much faster
Very Well Explained.Thanks bro.
Very helpful. Thank you for your videos!
Why aren't you at FAANG yet? Really like your simple yet thorough explanation! Thanks for the great videos!
you need to be able to reproduce this quality in a interview with random questions not study it beforehand and record a 10min video
So you understand his explanation?
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.
Hey Zoufishan! I just saw that, I'm sending you an invite now :)
Thank you. Simple and clearly explained.
👆🏼
i enjoyed watching this ! thanks so much for sharing it is well explained
Are these questions good for machine learning interviews or business analyst interviews too ?
these questions are too retarded to be asked for any type for interview
Hi Kevin, could you post more videos about DP?
This is the first video that makes sense, why does every other video talk about building a coins* amount memo table?
Hi Kevin, could you check the "Find the celebrity" video you posted before? It seems broken.
Could you add graph related problem
Great video and nice explanation. Made it very simple
good explanation, Kevin! You are the best
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?
not really, because sort would take O(nlongn) which is smaller than O(n*m) hence it would still be O(n * m)
No need to sort in this question. But complexity will be still same O(n*amount)
Why do we do amount + 1?
@Kevin, can you please post solution for " N balloon burst problem in leetcode"?
why 1 + ? . That’s important i think
I actually got asked this question, or one really close to it rather, in an interview the other day.
which company?
Kavish Pahade SnapDocs
Nice explanation sir thank you👍😊
Thanks Javid! :)
why i = 0 not 1? dp[0] is already min...isn't?
Great explanation! Thank you, Kevin.
Thanks Shiva and anytime!
Thank you so much for this video. ur the best kevin.
Great explanation :)
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?
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?
why everyone must work at FANG if they are good at leetcode?
After added the else break, some answers are wrong
I believe new test cases were added made this logic is incorrect?
Hey Kevin!
Thanks for the video. Can you please explain why at line 9, number 1 is added?
Because you're adding one additional coin to tally up from the previous solution, which was (amount - 1)
because the arre to store the result is 0 based.
@@ariellyrycs What does 0 based mean?
@@harrisonlu8532 I still dont get it.
What does dp mean?
dynamic programming
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];
}
Hey can u make a video on minesweeper and tic tac toe too ?
It would be helpful and greatly appreciated.
Nice explanations!
Amazing solution. It was way easeir than leetcode's solution. Thanks man!!
Can you please explain solution of diagonal traverse of 2D array? Leetcode 498
If this question asked in the interview, should we give the overview of recursion first or can we get started by dp?
id give quick explanation of recursion and then do dp and explain why you chose dp over recursion
@@alicebobson2868 Thanks
Great explanation!
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!
As additional explanation I suggest this video:
th-cam.com/video/jgiZlGzXMBw/w-d-xo.html
from Back to Back SWE.
I can't understand it, man.
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%.
dude, u are legend !
good job
Thank you so much
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;
}
if (amount % a == 0)
nuts explnation
Can you do the solution in c++? That will be very much helpful
lol, you just copy-paste solutions from leetcode :D
probably copied but not pasted, typed once again ;-)
Lol
@@notwhoyouthink666 I mean he explains it in an easy-to-understand manner thats helpful to people when a solution article might not be
@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.
Here's decent explanation on the greedy solution issue: th-cam.com/video/rdI94aW6IWw/w-d-xo.html