Love the Mask! and well, this one is a very nice and do-able DP problem. I was wondering if you could do #276 - Paint Fence? I couldn't do it for the life of me, and it's labelled as "Easy", so maybe I'm missing something and you can enlighten me. Thanks in Advance Kevin!
@@jlecampana Haha thanks and don't pay attention to the labels they're all subjective! I actually think I already have a video on that problem if you wanna check it out! And anytime, thank YOU for your support!!!
@@KevinNaughtonJr Oh I see it, you have done a video for LeetCode #256 - Paint House, How could I have missed it! I will see if I can actually solve the problem before watching your video. But I do think you should definitely check out #276, I could be wrong but I think it's Harder than most DP regulars. Have a nice day!
Purely Awesome! i'm kinda struggling with understanding the dynamic programming problems and this is the best explanation out here. Thank you once again for all your help.
Kevin, I've been following your tutorials since past couple of weeks. You don't need to doubt why do you have subscribers. Thank you for all the concepts.
We can improve this solution even further. We can use 3 variables instead of using a complete new array. Just like we do in fibonacci. Code- public int rob(int[] nums) { int loot1 = 0; int loot2 = 0; for (int i = 0; i
Very well explained. Below is the code in case if someone wants to try out. Both, with the dp[] array and without dp array. With dp[] array : O(n) Space class Solution { public int rob(int[] nums) { if(nums == null || nums.length == 0) return 0; if(nums.length == 1) return nums[0]; if(nums.length == 2) return Math.max(nums[0], nums[1]);
int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for(int i = 2; i < nums.length; i++) { dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]); } return dp[nums.length-1]; } } Without dp[] array : O(1) Space class Solution { public int rob(int[] nums) { if(nums == null || nums.length == 0) return 0; if(nums.length == 1) return nums[0]; if(nums.length == 2) return Math.max(nums[0], nums[1]);
int maxBeforeTwoHouse = nums[0]; int maxBeforeOneHouse = Math.max(nums[0], nums[1]); int maxAtI = Math.max(nums[0], nums[1]);
Hi Kevin nice explanation of dp. but we are sequentially processing so there is no need of dp array. if we change logic like this int first = nums[0]; int second = Math.max(nums[0],nums[1]); int ans = 0; for(int i=2; i
Thanks for doing the dynamic programming problems, I've been trying various difficulty ones for a while, and one of the things thats helped me the most has been watching your Leetcode videos, along with BackToBack SWE and Tushar Roy. I did something pretty similar to you in my Javascript solution, but did it in place, modifying the original input array. I think this could also be done in constant space and not modifying the input by using a variable to represent max up to i - 1 and max up to i - 2. Javascript solution ===== var rob = function(nums) { if (nums.length === 0) return 0; if (nums.length === 1) return nums[0]; for (let i=1; i
Hey Kevin, thank you for this! IMO, it's your best video to date :) I think you took the perfect amount of time to explain the logic before diving into the code; really clicked for me. Thank you!
This is the 1st dp problem for which I paused the video and got the DP logic on my own. This should be the 1st video to watch when you start learning DP. Initially I thought of 2 independent loops that calculates the sum of all odd and even plce elements, then take the max out of it. But this seems more optimized and useful for new concept.
I tried the odd/even thing as well first, but it will miss the max in some cases. Consider [8, 1, 9, 2, 5, 20] With checking odd vs. even, the max would be 23. However, the best robbery is 37. :)
Great intuition! A lot of people only keep 2 numbers (value if you robbed the house vs value if you didn't) and alternate saving the variables but I think that building the dp table is a lot more intuitive. We can also simplify the space complexity of the solution to be O(1) once we see the concept of building the table out in a real interview scenario
Hi Kevin, nice try. But your alogrithm would not return the correct answer in the following case : [2,1,3,4]. The answer should be 2+4 = 6. As both the locations are non-consecutive and lead to max loot. Hence, I tried solving this problem with recursion instead.
We actually don't need to check if nums.length==2 in the beginning. We are taking care of that in the loop itself. Anyway, loved the explanation. Love your videos man!
This is my first visit to this channel and it's really impressive.Thanks for sharing your knowledge !! I am going to watch at least one video everyday.
My Python solution: def rob(nums): dp = [0, 0] # having 0s instead of nums[0] and max(nums[:2]) handles cases where len(nums) is 0 or 1 or 2 for num in nums: dp.append(max(dp[-1], num + dp[-2])) return dp[-1]
I'm confused by the solution, can someone explain? I'm stuck understanding: dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]); Doesn't this mean we possibly have the chance of selecting an adjacent house instead of every other house?
Okay, im not sure if its this simple or not, but wouldn't the question devolve into checking whether the sum of the even numbered indices is greater than the odd? the only possible combos are all the even numbered indices and odd numbered indices. But i don' think its that easy
Thanks Grayson I really appreciate it and don't worry I'm not going anywhere! New video is uploading now so get ready to check it out. Thanks so much for your support!
I notice that you didn't use length + 1 for dp array this time, but for some other questions like number of coins and decoded ways all used length + 1 may I ask why this is otherwise?
1. great understandable DP explanation 2. love your freeze frame gold esp at 1:22 (that's some field theory sh*t I had to learn for cryptography 🤣) thanks for your helping me prep for my Google interview next week!
An improvement over this solution. Same as for Nth Fibonacci number. Without DP array. // T/S: O(n)/O(1) public int rob(int[] nums) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int twoBack = nums[0]; int oneBack = Math.max(nums[0], nums[1]); int curr = b; for (int i = 2; i < nums.length; i++) { curr = Math.max(nums[i] + twoBack, oneBack); twoBack = oneBack; oneBack = curr; } return curr; }
What if my sack where i put the money has a certain weight, and with each house's money there is a weight bounty i have to take into consideration, how would the program change ?
Hey, first of all I really like your videos the way you approach a dp problem makes it so soo simple. Thank you! Can you please make a video on Leetcode problem number 152, I just want to know how you will approach that problem in case you have time to do so!
Hey Kevin, your videos are very insightful and helping alot of people like me prepping up for the interviews. One thing I’d like to point in this question is that Is DP even necessary here? The first intuition that hit my mind when I read the question was to take the sum of the entire array (sum) and sum of all the alternate elements beginning from 0 (i.e. element at index 0 ,2, 4, till n-1 or n-2), lets call it X. The answer should be max(X , sum-X). Please let me know if there is something wrong in this approach ?
Hey, the question you have solved is, "maximum sum in an array such that no 2 elements are adjacent". I was asked this question in an interview, tell me how to solve this. Given an array and an int value K, find Maximum sum of numbers, such that no 2 elements are adjacent and sum not greater than K.
Every time you say "hopefully that's not too confusing" makes me start to assume the explanation you are about to make is going to be confusing haha. I really enjoy your videos, but I think the way you explain for some reason, it does not click for me. Maybe leetcode is still a little too complex for my programming level... I may just have to spend more time looking at the problems myself. Either way, thank you for having the solutions. I hope you answer every leetcode problem so we all have a reference solution for all the leetcode problems! Thank you again.
Ughh this is why I hate DP Problems. They always have a gotcha moment. It either clicks with us or it doesnt. I always had intuition that this was a DP problem before solving it but for some reason went towards the Brute Force and used many edge cases. Its hard to explain what I did and the problem worked for many cases but it failed many other cases. Anyhow, thanks for sharing again Kevin. Great work. Can you explain how you typically come up with solutions or algorithms to DP problems?
That's ok Atif it just takes practice keep working hard! What I normally try and do for dp problems is kinda what I did in this video...I try to think abou the simplest case. So whenever approaching a dp problem (and using bottom-up processing), I try to think about the absolute simplest case and build from there!
@@KevinNaughtonJr yea, true. I just need to tackle them more often until I can pick up exactly how to break down each problem into sub-problems. And as you said, it comes easier with practice. As always, thank you so much for this content and for replying.
The first three conditions are called as base conditions where only those situations will hold true. As Kevin has coded, nums has either 0,1 or 2 houses. If your nums is having more than 2 houses, we're gonna use a dynamic programming array and save the intermediate house value at each step. So, we would have to start again from 0, 1, and so on. Hope this helps!
It works without those base cases because we anyway have the values saved in the dp array. I was also wondering what made this dynamic programming problem different from the others I've seen from Kevin.
No need to store all values in dp array cuz in the for loop we are accessing only untill previous 2 values. public int rob(int[] nums) { if(nums==null || nums.length==0){ return 0; } if(nums.length==1){ return nums[0]; } if(nums.length==2){ return Math.max(nums[0],nums[1]); } int l3=nums[0]; int l2= Math.max(nums[0],nums[1]); int l1=0; for(int i=2;i
Hey Kevin: Can you please add videos related to longest common substring, longest common palindromic strings -- using dynamic programming and explaining it in bit detail, I am having issues understanding it. Thanks
HOW DOPE IS MY SKI MASK
Love the Mask! and well, this one is a very nice and do-able DP problem. I was wondering if you could do #276 - Paint Fence? I couldn't do it for the life of me, and it's labelled as "Easy", so maybe I'm missing something and you can enlighten me. Thanks in Advance Kevin!
@@jlecampana Haha thanks and don't pay attention to the labels they're all subjective! I actually think I already have a video on that problem if you wanna check it out! And anytime, thank YOU for your support!!!
@@KevinNaughtonJr Oh I see it, you have done a video for LeetCode #256 - Paint House, How could I have missed it! I will see if I can actually solve the problem before watching your video. But I do think you should definitely check out #276, I could be wrong but I think it's Harder than most DP regulars. Have a nice day!
@@jlecampana I'll check it out thanks for the suggestion!!!
Thanks Kevin for the best explanation of DP problem. I could use this example as a start for solving DP problems.
love the dp questions. i feel like i am starting to get it. thanks Kevin!
So so so so SO happy to hear that!
I saw this question in real interview and be able to do it. Thank you Kevin. :)
No way that's amazing anytime :)
Purely Awesome! i'm kinda struggling with understanding the dynamic programming problems and this is the best explanation out here. Thank you once again for all your help.
Kevin, I've been following your tutorials since past couple of weeks. You don't need to doubt why do you have subscribers. Thank you for all the concepts.
We can improve this solution even further. We can use 3 variables instead of using a complete new array. Just like we do in fibonacci. Code-
public int rob(int[] nums) {
int loot1 = 0;
int loot2 = 0;
for (int i = 0; i
This took me 2 hours and I'm reminded of how understanding key concepts is so efficient. Love your videos
thank you!
I love how you have the perfect camera window to block the previous tries of this question ;)
Very well explained. Below is the code in case if someone wants to try out. Both, with the dp[] array and without dp array.
With dp[] array : O(n) Space
class Solution {
public int rob(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
if(nums.length == 1)
return nums[0];
if(nums.length == 2)
return Math.max(nums[0], nums[1]);
int[] dp = new int[nums.length];
dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]);
for(int i = 2; i < nums.length; i++) {
dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
}
return dp[nums.length-1];
}
}
Without dp[] array : O(1) Space
class Solution {
public int rob(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
if(nums.length == 1)
return nums[0];
if(nums.length == 2)
return Math.max(nums[0], nums[1]);
int maxBeforeTwoHouse = nums[0];
int maxBeforeOneHouse = Math.max(nums[0], nums[1]);
int maxAtI = Math.max(nums[0], nums[1]);
for(int i = 2; i < nums.length; i++) {
maxAtI = Math.max(maxBeforeTwoHouse+ nums[i] , maxBeforeOneHouse);
maxBeforeTwoHouse = maxBeforeOneHouse;
maxBeforeOneHouse = maxAtI;
}
return maxAtI;
}
}
github.com/eMahtab/house-robber
Excellent Solution Kevin, cleared the concept of dp, through this explanation. Too Good, short, and on-point.
now, that's how you explain "SHIT" in a "BEAUTIFUL" way
Hi Kevin nice explanation of dp. but we are sequentially processing so there is no need of dp array. if we change logic like this
int first = nums[0];
int second = Math.max(nums[0],nums[1]);
int ans = 0;
for(int i=2; i
Bro, all those memes and explanations were lit!! Great Video :D
Thanks for doing the dynamic programming problems, I've been trying various difficulty ones for a while, and one of the things thats helped me the most has been watching your Leetcode videos, along with BackToBack SWE and Tushar Roy.
I did something pretty similar to you in my Javascript solution, but did it in place, modifying the original input array. I think this could also be done in constant space and not modifying the input by using a variable to represent max up to i - 1 and max up to i - 2.
Javascript solution
=====
var rob = function(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
for (let i=1; i
Hey Kevin, thank you for this! IMO, it's your best video to date :) I think you took the perfect amount of time to explain the logic before diving into the code; really clicked for me. Thank you!
The clearest video on this problem, thank you!
You don't need the if statement for the 2 houses case. Nice explanation, thanks!
Very nice explanation and approach . Thank you.
Awesome solution. Plz plz keep doing these tutorials. Love them!
This is the 1st dp problem for which I paused the video and got the DP logic on my own.
This should be the 1st video to watch when you start learning DP.
Initially I thought of 2 independent loops that calculates the sum of all odd and even plce elements, then take the max out of it.
But this seems more optimized and useful for new concept.
you cant use 2 for loops to solve the problem
I tried the odd/even thing as well first, but it will miss the max in some cases. Consider [8, 1, 9, 2, 5, 20] With checking odd vs. even, the max would be 23. However, the best robbery is 37. :)
that is unbelivable , how are u able to solve so easily dude.great work.
Thank you so much Sir 🌟 Awesome explanation out there.
Huge love and Respect from India 🌟🤗
@Kevin your solution explanation is simple and crystal clear, thanks a lot
The question starts with: You are a professional robber planning to rob houses along a street... That's a good start
Great intuition! A lot of people only keep 2 numbers (value if you robbed the house vs value if you didn't) and alternate saving the variables but I think that building the dp table is a lot more intuitive. We can also simplify the space complexity of the solution to be O(1) once we see the concept of building the table out in a real interview scenario
Thanks and definitely very good point!!!
the confusing part is how the dp array carries over the largest sum without overlapping sums and maintaining non adjacency
This is brilliant. Thank you!
Really Good Explentation
I think you got a dude moving in the background =)
yea creeped me out at 5:18
Hi Kevin, nice try. But your alogrithm would not return the correct answer in the following case : [2,1,3,4]. The answer should be 2+4 = 6. As both the locations are non-consecutive and lead to max loot. Hence, I tried solving this problem with recursion instead.
i was struggling with this problem for a day 😔 but your explanation was very intuitive! thank you!
We actually don't need to check if nums.length==2 in the beginning. We are taking care of that in the loop itself. Anyway, loved the explanation. Love your videos man!
Why do you have subscribers? lollll because you're awesome!
Crystal clear and neat explanation, good job as always 👍
Any referrence for dp? Where can I learn that? They don't teach it at school. lol
This is my first visit to this channel and it's really impressive.Thanks for sharing your knowledge !! I am going to watch at least one video everyday.
Anytime and thanks for the support!
You did a great job at explaining the concept properly!
Thanks Pranav!
My Python solution:
def rob(nums):
dp = [0, 0] # having 0s instead of nums[0] and max(nums[:2]) handles cases where len(nums) is 0 or 1 or 2
for num in nums:
dp.append(max(dp[-1], num + dp[-2]))
return dp[-1]
Oh! Hey when did you start programming?
@@yv6358 It's been 5 years since I started (in school), but I've become serious only from the last 1.5 years
@@saulgoodman980 What happened to your career in law?
@@yv6358 Oh xD
Well, you'll know in BCS S06 ;)
@@saulgoodman980 waiting for it
I'm confused by the solution, can someone explain?
I'm stuck understanding: dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
Doesn't this mean we possibly have the chance of selecting an adjacent house instead of every other house?
Bro this one was genius. Hats off for a great solution
devansh thanks dude
Awesome bro. This is the 3rd video I saw for this problem and now I actually could figure out the solution. Thanks.
Anytime Dhruv happy to hear the video was helpful :)
The robber is already sleeping in the background.:D
hahahah
Okay, im not sure if its this simple or not, but wouldn't the question devolve into checking whether the sum of the even numbered indices is greater than the odd?
the only possible combos are all the even numbered indices and odd numbered indices. But i don' think its that easy
Update : This is in medium now.
Nicely explained. Thank you
this question was asked in my interview and I'm not able to solve that, now it looks very simple to me. Dammmmm!!!
You're killing it, dude. Keep it up!
Thanks Grayson I really appreciate it and don't worry I'm not going anywhere! New video is uploading now so get ready to check it out. Thanks so much for your support!
Thank you Kevin!! Good and simplified explanation! :) This helped!
this problem can be solved by including first number from first index or excluding first number from first index and continue for the next indices.
I notice that you didn't use length + 1 for dp array this time, but for some other questions like number of coins and decoded ways all used length + 1 may I ask why this is otherwise?
How to identify if a certain problem's going to need dynamic problem to solve?
Very easy to understand. Thank you!
Anytime Kevin!
The explanation was really amazing
1. great understandable DP explanation
2. love your freeze frame gold esp at 1:22 (that's some field theory sh*t I had to learn for cryptography 🤣)
thanks for your helping me prep for my Google interview next week!
So, i guess you're a googleer now? :) Hope yes
@@SoferPeOZN unfortunately not :(
I'm an Amazonian tho!
simple and nice explanation.. i dont think we need an extra array.. i tried with the provided nums arrays and it worked.
Super explanation. Good to understand DP like this.
Awesome explanation of this question by a bottom up approach ..Can you explain it by a Top down ?
Do we need to create a new array? Can we overwrite the current array for O(1) space?
Kevin how many years of experienced have you had as a coder for using Java. Im intrested.
very intuitive, thanks!
Thank you for the explaination.
how do results not overlap, is there proof to this?
Very well explained intution! :) Thanks, this was of immense help!
Mihir Phatak thanks Mihir! Happy to hear the video was helpful :)
An improvement over this solution. Same as for Nth Fibonacci number. Without DP array.
// T/S: O(n)/O(1)
public int rob(int[] nums) {
if (nums.length == 0)
return 0;
if (nums.length == 1)
return nums[0];
int twoBack = nums[0];
int oneBack = Math.max(nums[0], nums[1]);
int curr = b;
for (int i = 2; i < nums.length; i++) {
curr = Math.max(nums[i] + twoBack, oneBack);
twoBack = oneBack;
oneBack = curr;
}
return curr;
}
What if my sack where i put the money has a certain weight, and with each house's money there is a weight bounty i have to take into consideration, how would the program change ?
Hey, first of all I really like your videos the way you approach a dp problem makes it so soo simple. Thank you! Can you please make a video on Leetcode problem number 152, I just want to know how you will approach that problem in case you have time to do so!
Hey Kevin, your videos are very insightful and helping alot of people like me prepping up for the interviews.
One thing I’d like to point in this question is that Is DP even necessary here? The first intuition that hit my mind when I read the question was to take the sum of the entire array (sum) and sum of all the alternate elements beginning from 0 (i.e. element at index 0 ,2, 4, till n-1 or n-2), lets call it X. The answer should be max(X , sum-X).
Please let me know if there is something wrong in this approach ?
[2,1,1,2] -> u need to rob 1st and last to get maximum
so nicely explained
Can we sort this array first and then start adding non adjacent elements from n-1 ?
If you sort the array first, you lose the original order and don't know what houses are adjacent anymore
Very helpful. Thanks!
What did you do on line 13? int[] dp = new int[nums.length] ? What is that?
It's java 😂
Hey, the question you have solved is, "maximum sum in an array such that no 2 elements are adjacent". I was asked this question in an interview, tell me how to solve this.
Given an array and an int value K, find Maximum sum of numbers, such that no 2 elements are adjacent and sum not greater than K.
damm
man, you made it look so easy...
Every time you say "hopefully that's not too confusing" makes me start to assume the explanation you are about to make is going to be confusing haha. I really enjoy your videos, but I think the way you explain for some reason, it does not click for me. Maybe leetcode is still a little too complex for my programming level... I may just have to spend more time looking at the problems myself. Either way, thank you for having the solutions. I hope you answer every leetcode problem so we all have a reference solution for all the leetcode problems! Thank you again.
If you want to save some extra space, we can just add the elements to the nums array. :)
This was asked by Bytedance as well, but I haven't seen the question before the interview :') . Hackerrank calls it boxes game instead.
Thank you! Really explained my struggles.
Great explanation! Just a question, we could probably shorten the last line to from dp[nums.length - 1] to dp[-1], right?
My greatest achievement was that I was able to find that it is a dp problem. Now I can relate to the solution, thanks :)
Nice!!!
can someone explain how this works with [4,1,1,4]
Awesome explanation mate!! thanks a lot!!
Swapnil Shukla anytime happy it was helpful!
Ughh this is why I hate DP Problems. They always have a gotcha moment. It either clicks with us or it doesnt. I always had intuition that this was a DP problem before solving it but for some reason went towards the Brute Force and used many edge cases. Its hard to explain what I did and the problem worked for many cases but it failed many other cases. Anyhow, thanks for sharing again Kevin. Great work. Can you explain how you typically come up with solutions or algorithms to DP problems?
That's ok Atif it just takes practice keep working hard! What I normally try and do for dp problems is kinda what I did in this video...I try to think abou the simplest case. So whenever approaching a dp problem (and using bottom-up processing), I try to think about the absolute simplest case and build from there!
@@KevinNaughtonJr yea, true. I just need to tackle them more often until I can pick up exactly how to break down each problem into sub-problems. And as you said, it comes easier with practice. As always, thank you so much for this content and for replying.
@@atift5465 Definitely, it's all about practice and anytime Atif thanks for your continued support :)
strange that the the recursive overlaping subsets gives a heap overflow error;
int Max_Rob(vector& nums,int i,int * dp){
if(i>=nums.size()){
return 0;
}
if(dp[i]!=0){
return dp[i];
}
return dp[i] = max(Max_Rob(nums,i+2,dp)+nums[i],Max_Rob(nums,i+3,dp)+nums[i+1]);
}
int rob(vector& nums) {
int dp[120] = {0};
return Max_Rob(nums,0,dp);
}
Awesome explanation
yes i have the same reaction when i understand DB
Thanks a tonne Kevin!
how does the 1st 3 condition making a diff, can we not directly start by setting dp[0] and dp[1]
The first three conditions are called as base conditions where only those situations will hold true.
As Kevin has coded, nums has either 0,1 or 2 houses.
If your nums is having more than 2 houses, we're gonna use a dynamic programming array and save the intermediate house value at each step. So, we would have to start again from 0, 1, and so on.
Hope this helps!
It works without those base cases because we anyway have the values saved in the dp array. I was also wondering what made this dynamic programming problem different from the others I've seen from Kevin.
Now this question become Leetcode medium. Still Dope mask and video.
Omg I really like ur bgm at the beginning!!
thanks Yi!
You are awesome man, Neat & clear, keep it up bro
god tier thumbnail
Hey kevin , how would u go about to reduce the memory usage in this question ?
No need to store all values in dp array cuz in the for loop we are accessing only untill previous 2 values.
public int rob(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
if(nums.length==2){
return Math.max(nums[0],nums[1]);
}
int l3=nums[0];
int l2= Math.max(nums[0],nums[1]);
int l1=0;
for(int i=2;i
Hey Kevin: Can you please add videos related to longest common substring, longest common palindromic strings -- using dynamic programming and explaining it in bit detail, I am having issues understanding it. Thanks
I'll see what I can do, thanks for the suggestion!
you can go through Aditya Verma Dynamic Programming videos. He has explained all those concepts very nicely.
Thank you
you are a life saver
Thanks, great solution!
Clear and concise. but if possible, can you draw out an example and follow through with your code next time?
This isn't the optimal, constant space solution.
loved it!
Wow finally a good explanation
thanks!
I like the music youre using!
ronald abellano thanks Ronald!!!