Coin Change

[@KevinNaughtonJr]

What question should I cover next?

[@MohammedJavid-jz8vi]

Sir please try to cover questions related to binary trees👍

[@KevinNaughtonJr]

@@ismailelhabbash I'll add that to my list!

[@KevinNaughtonJr]

@@MohammedJavid-jz8vi You've got it Javid!

[@kuppurajkarthik]

Can you do Word Squares and Sliding window maximum?

[@KevinNaughtonJr]

@@kuppurajkarthik I'll add it to my list! Do you have the problem numbers?

[@BABEENGINEER]

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.

[@CASLOAcademy]

you should pay him to do that. he is not your slave....

[@Karan-zk9ke]

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

[@kuppurajkarthik]

Your solutions always make it look so simple compared to Leetcode or GeeksforGeeks. Great work!!

[@KevinNaughtonJr]

Thanks Kuppuraj I'm happy to hear my explanations are helpful :)

[@notwhoyouthink666]

His solutions are just copy-paste from solution tab on leetcode.

[@pradeepkumar-qo8lu]

@@notwhoyouthink666 doesn't matter, he's explaining it in a matter that is digestible for Noobs like me

[@abdoulbarry6929]

Ikrrrrrrrrrrrr....this gives me faith to keep working on my skills!!! Such a great teacher

[@jameysiddiqui6910]

@@notwhoyouthink666 u can also do the same, please try to appreciate someone's effort instead of negativity.

[@pmolchanov2002]

I like how you are using a bottom-up approach to DP instead of recursion. It makes your code much cleaner and simple!

[@abzzz4u]

How come you make it look so easy? Genius.

[@pvsk10]

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 😊

[@JohnWick-ep7qr]

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;

[@KevinNaughtonJr]

thanks John and yes nice catch!

[@joetxca]

Line 17, "dp[amount] > amount ? -1 : dp[amount]" does dp[amount] > amount comparable?

[@lawrencejustin8136]

Hi Kevin, do you have a playlist of all your dynamic programming leetcode solutions?

[@Nikhil-gm8ks]

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

[@rahuljain5642]

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

[@fsfdsdfdsfsdf]

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!

[@samarpanharit4268]

As far as i know , DP is mainly used for optimisation problems(minimisation or maximising) .

[@harrisonlu8532]

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.

[@zustaz]

Thanks for a great video! Why we can't use greedy approach here?

[@vernon_4411]

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.

[@mrodg]

This wouldn't work don't waste your time.

[@ariellyrycs]

i tryied that approach, but it timed out.

[@anisharbi3510]

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.

[@pjamestx]

@@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.

[@budguesor9222]

@@pjamestx The amount is 8 not 4 for the example anis gave.

[@sandarabian]

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?

[@trintron65]

i - coins[j] will never be negative, because there is a condition check (coin[j]

[@shobananatesan]

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?

[@stage666]

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?

[@alisazhila4458]

What a dedication to teaching, almost losing breath! The video is much appreciated though! :)

[@AnkitMishra-xu6ef]

Sir, Your solutions are always very easy to understand compared to the other online resources. Thanks for it.

[@ketulshah5283]

I still didn't understand login on line number 9. Can someone explain deeper?

[@joetxca]

Line 17, "dp[amount] > amount ? -1 : dp[amount]" does dp[amount] > amount comparable?

[@vk1618]

Bottom up approach + optimization by removing obvious no-fits

[@jadenwatt1977]

how do you come up with this, inspirational fr lmao

[@nasirkhansirajbhai8016]

can someone pls explain line # 9, I still didn't get it

[@rufortian1084]

Thank you so much, these explanations are really great!

[@KelleyKouture]

this is a FANTASTIC explanation!!! thank you so much!!!

[@KevinNaughtonJr]

anytime Alyssa and thanks!

[@barkhabajaj5596]

Hi Kevin, Can you please add Snake and Ladders problem. I know its an easy one, but like to see your approach. Thanks

[@ariellyrycs]

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.

[@williamalexander5371]

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

[@EchoVids2u]

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.

[@AbhishekRanjanUIUC]

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?

[@KevinNaughtonJr]

Thanks and I'll see what I can do!

[@undergraddeveloper1130]

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.

[@ParitoshPotukuchi]

{1,3,4,5} and sum=7. do it yourself!!!

[@BadriBlitz]

Very Well Explained.Thanks bro.

[@RenatoFontes]

Took me a while to understand but the solution is perfect. Thanks!

[@adityagupta375]

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?

[@playanakobi4407]

One problem I always get when solving these is how do I get the subproblem. Thank you for this!

[@quangvo4563]

Why do we have to have the "+1" at dp[i] = Min(dp[i], 1 + dp[i-coins[j]]

[@rongav1997]

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]

[@rickvideoone]

because we are taking "1" coin of value: coin[j].

[@Saikumar-kb4lf]

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)

[@gcash49]

this wudnt pass all test cases for this problem

[@neerajkumar1993]

You good man..you good! Struggled with this guy for a lil

[@PedroGrilo13]

Very helpful. Thank you for your videos!

[@CyberMew]

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.

[@alamjim6117]

What a underrated channel?!!!

[@nosoyyotampoco]

Hi Kevin, could you post more videos about DP?

[@ermattson]

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.

[@joelogtheta640]

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]);

[@machsleep]

Thank you. Simple and clearly explained.

[@bestplatformtoearnfastbolt9582]

👆🏼

[@sateeshtata]

Love the explanation and the optimization tip in the end. Thanks for making the video.

[@phouthasakinit]

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?

[@olakunleism]

not really, because sort would take O(nlongn) which is smaller than O(n*m) hence it would still be O(n * m)

[@विशालकुमार-छ7त]

No need to sort in this question. But complexity will be still same O(n*amount)

[@SelftaughtSoftwareEngineer]

Why aren't you at FAANG yet? Really like your simple yet thorough explanation! Thanks for the great videos!

[@vaichegodas]

you need to be able to reproduce this quality in a interview with random questions not study it beforehand and record a 10min video

[@codegeek8256]

So you understand his explanation?

[@pegahfallah3770]

first video of this problem that i actually understood ty

[@lifeofme3172]

Why do we do amount + 1?

[@vaishnavibollaboina6620]

Are these questions good for machine learning interviews or business analyst interviews too ?

[@walidzein1]

these questions are too retarded to be asked for any type for interview

[@angrwl]

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?

[@MohammedJavid-jz8vi]

Nice explanation sir thank you👍😊

[@KevinNaughtonJr]

Thanks Javid! :)

[@calfland79]

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.

[@iPoopDinosaurs]

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]

[@jonfit2392]

@@iPoopDinosaurs Got it. Thanks.

[@codegeek8256]

What does dp mean?

[@mrbobcat7399]

dynamic programming

[@sleepingguru3243]

Could you add graph related problem

[@krithickkrishnagiri6371]

Great video and nice explanation. Made it very simple

[@son0funiverse]

I don't get it Amazon boy. please help

[@nnelg.t1232]

This dude is gold

[@nagavedareddy5891]

Great explanation :)

[@jmackultra]

I actually got asked this question, or one really close to it rather, in an interview the other day.

[@kavishpahade1337]

which company?

[@jmackultra]

Kavish Pahade SnapDocs

[@chickentowel-ek]

Hi Kevin, could you check the "Find the celebrity" video you posted before? It seems broken.

[@aviroxi]

really i don't know what leetcode is but after watching this video i am addicted to it thank you so much

[@pauleaggymandengue3135]

i enjoyed watching this ! thanks so much for sharing it is well explained

[@reallylordofnothing]

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.

[@swethavarnaau7619]

Thank you so much for this video. ur the best kevin.

[@fabiocosta3003]

good explanation, Kevin! You are the best

[@manikandantv3015]

@Kevin, can you please post solution for " N balloon burst problem in leetcode"?

[@blaisemuhirwa7806]

Nice explanations!

[@juicee235]

Great explanation!

[@KevinNaughtonJr]

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!

[@ShailPanchal]

If this question asked in the interview, should we give the overview of recursion first or can we get started by dp?

[@alicebobson2868]

id give quick explanation of recursion and then do dp and explain why you chose dp over recursion

[@ShailPanchal]

@@alicebobson2868 Thanks

[@Artificial_Intelligence_AI]

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

[@knight_23]

I was also thinking the same

[@TZCoder]

This is the first video that makes sense, why does every other video talk about building a coins* amount memo table?

[@caesar5555]

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

[@piglets_1992]

Hey Kevin! Thanks for the video. Can you please explain why at line 9, number 1 is added?

[@harrisonlu8532]

Because you're adding one additional coin to tally up from the previous solution, which was (amount - 1)

[@ariellyrycs]

because the arre to store the result is 0 based.

[@codegeek8256]

@@ariellyrycs What does 0 based mean?

[@codegeek8256]

@@harrisonlu8532 I still dont get it.

[@shiva_bhusal]

Great explanation! Thank you, Kevin.

[@KevinNaughtonJr]

Thanks Shiva and anytime!

[@alex.perreras]

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

[@zoufishanmehdi]

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.

[@KevinNaughtonJr]

Hey Zoufishan! I just saw that, I'm sending you an invite now :)

[@sars-cov-2611]

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%.

[@ej9806]

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?

[@chenyangwang7232]

why everyone must work at FANG if they are good at leetcode?

[@adi_sekar]

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?

[@hanif3661]

why 1 + ? . That’s important i think

[@johnangelo2000]

why i = 0 not 1? dp[0] is already min...isn't?

[@nosoyyotampoco]

After added the else break, some answers are wrong

[@chenyangwang7232]

I believe new test cases were added made this logic is incorrect?

[@friendsforevere3637]

Hey can u make a video on minesweeper and tic tac toe too ? It would be helpful and greatly appreciated.

[@lauaurora66]

dude, u are legend !

[@giorgi23]

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]; }

[@vasanthkannan3398]

I can't understand it, man.

[@RishabhVerma]

Can you please explain solution of diagonal traverse of 2D array? Leetcode 498

[@studyaccount794]

Amazing solution. It was way easeir than leetcode's solution. Thanks man!!

[@doruwyl]

As additional explanation I suggest this video: kzbin.info/www/bejne/oJjMi599r72AeNk from Back to Back SWE.

[@AmolGautam]

Thank you so much

[@alirezaRahmanikhalili]

good job

[@anshuman5554]

Can you do the solution in c++? That will be very much helpful

[@harrypotter-ku4lf]

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; }

[@harrypotter-ku4lf]

if (amount % a == 0)

[@ahmedbrhili1965]

nuts explnation

[@notwhoyouthink666]

lol, you just copy-paste solutions from leetcode :D

[@algoseekee]

probably copied but not pasted, typed once again ;-)

[@notwhoyouthink666]

Lol

[@fsfdsdfdsfsdf]

@@notwhoyouthink666 I mean he explains it in an easy-to-understand manner thats helpful to people when a solution article might not be

[@roblevintennis]

@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.

[@roblevintennis]

Here's decent explanation on the greedy solution issue: kzbin.info/www/bejne/qJWsameXjJt8jdk