Coin Change (LeetCode 322) | Full solution with beautiful diagrams and visuals | Simplified

To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
One cannot emphasize enough how important this problem is. Almost asked in every tech company at every level of interview as it tests your critical thinking ability and how well you understand dynamic programming. This video show a step by step approach, how you can attack and solve such problems with beautiful animations and diagrams. You will never remember the solution by heart and never forget it again.
Actual problem on LeetCode: leetcode.com/problems/coin-ch...
Chapters:
00:00 - Intro
01:11 - Problem Statement and Description
03:35 - Brute Force Solution is not optimal
04:21 - A greedy approach does not work
07:15 - Building a dynamic programming solution
18:50 - Dry-run of Code
20:51 - Final Thoughts
📚 Links to topics I talk about in the video:
LeetCode Problems: • Leetcode Solutions
Other medium difficulty problems: • Medium Problems
Dynamic Programming: • Dynamic Programming ea...
0/1 Knapsack Problem: • 0/1 Knapsack Problem e...
Greedy Algorithms: • Greedy Algorithms with...
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

[@boisaulit]

Looked at neetcode's solution 3 times and didn't undertand it. Here I understand it the first time. Thank you!

[@kartikforwork]

because he explain top down approach

[@maninform3523]

@@kartikforworkhe did bottom up also but his was too complicated to me

[@AndyBnq]

True, his explanation is better than neetcode's for this problem and several others.

[@amansahil2725]

Dude you deserve more subscribers Wonderful explanation

[@codeforfreedom]

Gotcha, you finally made me understand that. After looking 3 different other videos and still was completely lost, thank you.

[@ellenstuder4269]

like everyone else, this was the first explanation of this problem (and dynamic programming in general) that made any sense to me. thank you!!

[@duyviet5801]

I was so happy whenever I search a problem on Leetcode and find your video !

[@huaqian3654]

Best explanation ever! I was really struggling with this one. Big thank-you to you sir!

[@krrishh7]

Nice explanation of the concept. Keep doing more such videos. ❤ However, just wanted to add a small detail here (in favour of others checking as well). It would be good if we could also initialise minCoinsDp[0] to 0 explicitly. As to reach amount 0, fewest number of coins is 0. Since its java code, I think it gets initialised automatically to 0, but for other primitive languages like c,c++ we need an initialiser and the loop in the example code is only running from i=1 (skipping 0). vector minCoinsDp(amount+1, INT_MAX); // default initialise all to INT_MAX minCoinsDp[0]=0; // special case If the code can be adjusted as above, all such ambiguity can be cleared.

[@yomamasofat413]

ikr? In javascript it's initialized to NaN

[@parth2497]

Cleanest solution I could find for this problem. Thank you !

[@nikoo28]

Great to hear!

[@bookflexapp4804]

Best explanation ever! Thank you!

[@vivekkumaryadav9862]

A big Thanks to you sir...bht better way se apne explain kiya..

[@mamtayadav6195]

Really Good Explanation! Thankyou.

[@user-sr5bw5gg8n]

underated youtuber , u deserve views in millions brother

[@nandhakumarkr3147]

Great intention and good patience in explaining the approach. Kudos 🎉

[@nikoo28]

thanks for the support..will keep making more videos.

[@user-tm8xm9eb3z]

Respect, i love iterative explanations.

[@user-wo4dt2qt3s]

Thank you so much sir for such nice explainations.

[@yashthakur5712]

Finally understood the code crystal clear

[@ivandrofly]

Fully understand this problem now- I would say the stairs claiming is also a good one to check if you stuck here

[@nikoo28]

Yes, that is a similar one

[@Amarsri19]

Thanks for the visualization which brings more clarity.

[@nikoo28]

yep, visuals are easy to remember.

[@dhineshbabu9376]

👯 Finally, a video to understand this method 🥳🥳🥳

[@vanaparthibullisiva5739]

Sir , I started watching your lecture series. I am able to understand very well but sometimes it is bit difficult to understand the coding part even though we understood the theory. Sir ,no one can beat u in the explanation of the theory. Spend some more time to explain code. It is reallly useful for us..I suggested my friends to watch this series..very useful series I say.❤

[@nikoo28]

the thing is that today you have a lot of GPTs that can write the code for you. writing code in any language is no longer a challenge in my opinion. However, problem solving is and will always be the most important aspect. If you are understanding the solution correctly step by step, you will be able to write the code eventually. It is just a matter of time. To get the best learning, I would highly encourage you to write the code yourself, do not copy the provided code. :) All the very best for your goals!!

[@vcs649]

fantastic intuition

[@pandeyshashidhar]

Thank You sooooooooooooo much

[@shubhammanecr7]

Thanks for posting!

[@nikoo28]

You're welcome

[@sonofgod00]

thanks bhai

[@GopiKrishnasWorld]

Thanks!

[@nikoo28]

Thanks for the support 😄

[@divypareek8230]

great video

[@Rob-J-BJJ]

great explanationn my brother just wish you would've gone through the if condition you have in the last part, because I know it gets the min, but I wanted to see it explained how

[@nikoo28]

that is just comparison to get the minimum number. What are you struggling with?

[@bishwashkumarsah171]

Your explanation is awesome sir.. but during that dry run code i was little confused...i was expecting u to tell about the for loop using some dry run....That was just my opinion..

[@nikoo28]

I understand...but I realized that the video already went too long, going over each step in the code would take another 10 minutes. If you follow the logic as explained, writing the for loop should not be tricky at all. What part of the loop are you facing a problem with? I can elaborate more as needed :)

[@anniamatthews6803]

@@nikoo28 could you please explain the loop where you look through the coins and what exactly you are doing? I'm a little new to DP and I understand the solution but the implementation is a little fuzzy.

[@nikoo2805]

What part of the loop are you facing a problem with?

[@prashikmanwar2109]

Beautiful explanation bhaii..!!

[@nikoo28]

It's my pleasure

[@Chriscs7]

Can you write a code that finds the minimum number of coins and also prints the actual coins used ?

[@arpitrathore354]

Can we solve this problem using 2-D DP by taking two changing variables length of array and amount????

[@nikoo28]

try outlining a pseudo code/algorithm

[@shwetathakare1556]

Best ❤

[@tamils12345]

Hello, Can you share your studio setup ? what are the tools you use for drawing, editing?

[@nikoo28]

Sure..I can elaborate more..but here was a sneak peek: kzbin.infoh2oCQmwvv94?feature=share

[@syedaafreen1075]

Amazing

[@ganeshktvb9234]

Sir , im struggling to come up with dp solutions for a questions.so initially im solving with recursion and then memoizing and then converting it into dp. Is it ok or shoul i change my approach ?❤

[@nikoo28]

it is a very good approach indeed if you can think with all different methods. Will often lead you to the best choice. Your approach is correct. With practice you will be able to identify patterns and come up with solutions naturally. All the very best.

[@ganeshktvb9234]

@@nikoo28 thanks for reply sir❤️

[@cagarwal]

I struggled for the whole day to be able to solve this problem. I could write the code by myself after watching how to fill in the array. One request - Can you make a video of solving the same problem using recursion?

[@nikoo28]

i generally tried to avoid recursion. It is very very confusing...also every recursive problem can be solved iteratively. :)

[@harshitkumar8988]

@@nikoo28 No Sir please make a video on recursion your teaching level is just wow understand all dp problem but unable to understand a recursion its request sir to make video on it.

[@nikoo28]

@@harshitkumar8988 Why do you want to solve it using recursion?

[@harshitkumar8988]

@@nikoo28 Sir because i want from brute force to space optimization and tbh i didn't understand the concept of recursion i have solve approx 30 to 35 question on recursion but i didn't get it and the way you solve this problem is phenomenon . So if u use some sort of recursion explanation in between the lecture . That will be great

[@ayushmehta0113]

explanation was 10/10 but you should once explain the code also using the same example line by line

[@nikoo28]

it is hard to explain line by line...everyone has a different coding style. If you understand the explanation, you should try to write the solution on your own.

[@SivaSiva-wi2q]

cant understand the logic u coded in the code...please explain that too in step by step

[@MadpolygonDEV]

What would a brute force solution look like? Having a hard time visualising a bruteforce solution

[@nikoo28]

a brute force approach would involve generating all possible combinations of coins to find the minimum number of coins needed to make up the target amount. public int coinChange(int[] coins, int amount) { int result = backtrack(coins, amount); return (result == Integer.MAX_VALUE) ? -1 : result; } private int backtrack(int[] coins, int remainingAmount) { if (remainingAmount == 0) { return 0; } if (remainingAmount < 0) { return Integer.MAX_VALUE; // Return a large value to indicate invalid solution } int minCoins = Integer.MAX_VALUE; for (int coin : coins) { int subproblemResult = backtrack(coins, remainingAmount - coin); minCoins = Math.min(minCoins, subproblemResult + 1); } return minCoins; }

[@HistoryHouse45]

sir could you please explain word break problem

[@nikoo28]

i have that problem in my pipeline of videos. Will add it soon

[@ravilalachinnaraghavulu8207]

Coine piker gurunchi app lo vache nebaru details anga tamobola

[@user-rf5hv2up2g]

When bro explains something it sticks forever.

[@yashthakur5712]

Sir the explanation was excellent but pls explain the code because I am not able to understand that why are we writing as the code is.

[@nikoo28]

what part are you facing a problem with?

[@ashishkumarshawhitchem2017]

we want full dp playlist

[@nikoo28]

yes yes yes...adding more questions soon :)

[@mmm-ie5ws]

the code part which is the most important part isnt explained well at all.

[@nikoo28]

Sorry if you felt that way...but I want to focus my channel on understanding the problem rather than writing code. I believe that if you have good problem solving skills, writing code is very trivial. There are a lot more channels who do a better job at writing the code :)

[@ankitsrivastava2994]

​@@nikoo28means we should look other's solution instead so rude you are

[@nikoo28]

Always remember that languages will continue to change and evolve with time. The concept and the logic will remain forever the same. :) So, in order to become a better coder, I would highly recommend you to try writing the code on your own. 😃 If you are still interested to know how the code is working, use a debugger and iterate through the values. This way you will always be a better leaner.

[@siddharthmehta4223]

good approach, but the worst explanation of the code that you have written., please explain what does every line means after the second for loop. 🤫😕

[@nikoo28]

what part of the code are you facing problems with? If you understand the solution perfectly writing the code for it should be trivial. We do exactly the same thing...using a for loop take one coin at a time and determine the minimum required. :)

[@varshinikaithapuram6189]

what is the use of putting Integer.MAX_VALUE here?

[@nikoo28]

Just a sentinal value to make writing the code easier.