Coin Change (LeetCode 322) | Full solution with beautiful diagrams and visuals | Simplified
Vložit
- čas přidán 14. 07. 2024
- 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
Looked at neetcode's solution 3 times and didn't undertand it. Here I understand it the first time. Thank you!
because he explain top down approach
@@kartikforworkhe did bottom up also but his was too complicated to me
True, his explanation is better than neetcode's for this problem and several others.
Gotcha, you finally made me understand that. After looking 3 different other videos and still was completely lost, thank you.
Best explanation ever! I was really struggling with this one. Big thank-you to you sir!
I was so happy whenever I search a problem on Leetcode and find your video !
like everyone else, this was the first explanation of this problem (and dynamic programming in general) that made any sense to me. thank you!!
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.
Best explanation ever! Thank you!
A big Thanks to you sir...bht better way se apne explain kiya..
Cleanest solution I could find for this problem. Thank you !
Great to hear!
Respect, i love iterative explanations.
underated youtuber , u deserve views in millions brother
Finally understood the code crystal clear
Really Good Explanation! Thankyou.
Dude you deserve more subscribers
Wonderful explanation
Thank you so much sir for such nice explainations.
Great intention and good patience in explaining the approach. Kudos 🎉
thanks for the support..will keep making more videos.
👯 Finally, a video to understand this method 🥳🥳🥳
Thanks for the visualization which brings more clarity.
yep, visuals are easy to remember.
Fully understand this problem now- I would say the stairs claiming is also a good one to check if you stuck here
Yes, that is a similar one
fantastic intuition
Thank You sooooooooooooo much
Thanks for posting!
You're welcome
great video
Beautiful explanation bhaii..!!
It's my pleasure
Thanks!
Thanks for the support 😄
thanks bhai
Best ❤
Amazing
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
that is just comparison to get the minimum number. What are you struggling with?
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..
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 :)
@@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.
What part of the loop are you facing a problem with?
explanation was 10/10 but you should once explain the code also using the same example line by line
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.
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?
i generally tried to avoid recursion. It is very very confusing...also every recursive problem can be solved iteratively. :)
@@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.
@@harshitkumar8988 Why do you want to solve it using recursion?
@@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
Can we solve this problem using 2-D DP by taking two changing variables length of array and amount????
try outlining a pseudo code/algorithm
Can you write a code that finds the minimum number of coins and also prints the actual coins used ?
Hello, Can you share your studio setup ? what are the tools you use for drawing, editing?
Sure..I can elaborate more..but here was a sneak peek:
czcams.com/users/shortsh2oCQmwvv94?feature=share
What would a brute force solution look like? Having a hard time visualising a bruteforce solution
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;
}
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 ?❤
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.
@@nikoo28 thanks for reply sir❤️
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.
what part are you facing a problem with?
sir could you please explain word break problem
i have that problem in my pipeline of videos. Will add it soon
the code part which is the most important part isnt explained well at all.
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 :)
@@nikoo28means we should look other's solution instead
so rude you are
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.
we want full dp playlist
yes yes yes...adding more questions soon :)
Coine piker gurunchi app lo vache nebaru details anga tamobola
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. 🤫😕
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. :)
what is the use of putting Integer.MAX_VALUE here?
Just a sentinal value to make writing the code easier.