What question should I cover next?

@MohammedJavid-jz8vi

5 жыл бұрын

Sir please try to cover questions related to binary trees👍

@KevinNaughtonJr

5 жыл бұрын

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

@KevinNaughtonJr

5 жыл бұрын

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

@kuppurajkarthik

5 жыл бұрын

Can you do Word Squares and Sliding window maximum?

@KevinNaughtonJr

5 жыл бұрын

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

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

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.

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

2 жыл бұрын

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

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?

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

@KevinNaughtonJr

5 жыл бұрын

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

@notwhoyouthink666

5 жыл бұрын

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

@pradeepkumar-qo8lu

4 жыл бұрын

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

@abdoulbarry6929

3 жыл бұрын

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

@jameysiddiqui6910

3 жыл бұрын

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

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

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 😊

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

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

4 жыл бұрын

thanks John and yes nice catch!

@joetxca

2 жыл бұрын

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

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

How come you make it look so easy? Genius.

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

Thank you so much, these explanations are really great!

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

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

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

4 жыл бұрын

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

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

@KevinNaughtonJr

4 жыл бұрын

anytime Alyssa and thanks!

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

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

4 жыл бұрын

Thanks and I'll see what I can do!

how do you come up with this, inspirational fr lmao

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

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

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

5 жыл бұрын

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

@harrisonlu8532

5 жыл бұрын

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.

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?

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

4 жыл бұрын

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

@user-tx3mo1ez2n

2 жыл бұрын

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

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 dp[i]=min(dp[i], 1 + dp[i - coin]);

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

Bottom up approach + optimization by removing obvious no-fits

Very helpful. Thank you for your videos!

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

4 жыл бұрын

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

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

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

Hi Kevin, could you post more videos about DP?

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

good explanation, Kevin! You are the best

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

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

4 жыл бұрын

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

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.

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

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

@walidzein1

3 жыл бұрын

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

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?

Great video and nice explanation. Made it very simple

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

first video of this problem that i actually understood ty

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?

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

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

Great explanation! Thank you, Kevin.

@KevinNaughtonJr

4 жыл бұрын

Thanks Shiva and anytime!

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

2 жыл бұрын

this wudnt pass all test cases for this problem

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?

Very Well Explained.Thanks bro.

Nice explanations!

Thank you. Simple and clearly explained.

@bestplatformtoearnfastbolt9582

2 жыл бұрын

👆🏼

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

@vaichegodas

4 жыл бұрын

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

2 жыл бұрын

So you understand his explanation?

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

Great explanation :)

Nice explanation sir thank you👍😊

@KevinNaughtonJr

5 жыл бұрын

Thanks Javid! :)

dude, u are legend !

This dude is gold

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

@harrisonlu8532

5 жыл бұрын

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

@ariellyrycs

4 жыл бұрын

because the arre to store the result is 0 based.

@codegeek8256

2 жыл бұрын

@@ariellyrycs What does 0 based mean?

@codegeek8256

2 жыл бұрын

@@harrisonlu8532 I still dont get it.

As additional explanation I suggest this video: kzread.info/dash/bejne/nJudvM6Aqruzcto.html from Back to Back SWE.

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

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

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

@rongav1997

4 жыл бұрын

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

4 жыл бұрын

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

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.

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

5 жыл бұрын

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

What a underrated channel?!!!

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

4 жыл бұрын

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

@ariellyrycs

4 жыл бұрын

i tryied that approach, but it timed out.

@anisharbi3510

4 жыл бұрын

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

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.

@budguesor9222

3 жыл бұрын

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

Why do we do amount + 1?

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

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

@kavishpahade1337

3 жыл бұрын

which company?

@jmackultra

3 жыл бұрын

Kavish Pahade SnapDocs

Great explanation!

@KevinNaughtonJr

3 жыл бұрын

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!

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.

Could you add graph related problem

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

@alicebobson2868

4 жыл бұрын

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

@ShailPanchal

4 жыл бұрын

@@alicebobson2868 Thanks

I don't get it Amazon boy. please help

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

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]

@jonfit2392

4 жыл бұрын

@@iPoopDinosaurs Got it. Thanks.

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

4 жыл бұрын

I was also thinking the same

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

4 жыл бұрын

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

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

What does dp mean?

@mrbobcat7399

2 жыл бұрын

dynamic programming

good job

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

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

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

why 1 + ? . That’s important i think

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

Thank you so much

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

I can't understand it, man.

After added the else break, some answers are wrong

@chenyangwang7232

4 жыл бұрын

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

nuts explnation

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

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

3 жыл бұрын

if (amount % a == 0)

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

@algoseekee

5 жыл бұрын

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

@notwhoyouthink666

5 жыл бұрын

Lol

@fsfdsdfdsfsdf

5 жыл бұрын

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

@roblevintennis

4 жыл бұрын

@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

4 жыл бұрын

Here's decent explanation on the greedy solution issue: kzread.info/dash/bejne/pJh9m5aah5mvh9o.html