House Robber | Recursion | Memo | Bottom Up | Leetcode 198
Вставка
- Опубліковано 12 вер 2024
- This is the 9th Video on our Dynamic Programming (DP) Playlist.
In this video we will try to solve another very very famous DP Problem "House Robber" also known as "Stickler Thief"
We will try to understand how we come up with the DP approach. The intuition behind it. And see time and space complexity.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : House Robber
Company Tags : Amazon, OYO Rooms, Paytm, Walmart, Google, Flipkart, LinkedIn, Airbnb
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
Really good way of explanation,
Waiting for the day when you will start DSA lectures on UA-cam that will bring disaster for sure 🤘🤘
Thanks a lot Manish ❤️❤️❤️
time flys away watching this superb explanation, Carry on with this 💪💪
Thanks a lot Chinmay ♥️♥️♥️
bhaiya jaisa aapne bottom up samjhaya hai na maza aa gaya ..hazaro videos dekhe lekin kabhi samajh nhi aaya lekinn aapne samjha diya
Can't wait to see your lectures on DSA.
Soon
Thanks a lot for watching Priyanshu ❤️❤️❤️
One suggestion!
The bottom up approach can be space optimized from SC(n) to SC(1). As we are utilizing only previous two max values, it can only be stored in two integer variables.
CPP solution:-
class Solution {
public:
int rob(vector& nums) {
int n = nums.size();
if(n == 1) return nums[0];
int prev2 = 0; // house array [prev2, prev1, current_house]
int prev1 = nums[0];
int maxsteal = 0;
for(int i=2;i
Definitely. Thanks a lot for sharing ❤️🙏
This is by far the best channel I found who goes to all the depth of any problem. Thanks a lot man
Bhai ka mast samjate ho app maja aagaya. 💝🚀
Thanks a lot 😇❤️
your video is always on priority.
Katai lajawab.😎
the first approach i thought of without properly understanding the qn but seeing the constraints was this which is wrong.
class Solution {
public int rob(int[] nums) {
int maxi = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j += 2) {
sum += nums[j];
}
maxi = Math.max(maxi, sum);
}
return maxi;
}
}
Then I realised we can skip multiple houses and wrote the similar code as yours :
class Solution {
int maxi = Integer.MIN_VALUE;
public int rob(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, -1);
maxi = helper(nums, 0, dp);
return maxi;
}
public int helper(int[] arr, int i, int[] dp) {
if (i >= arr.length) return 0;
if (dp[i] != -1) return dp[i];
int take = arr[i] + helper(arr, i + 2, dp);
int notTake = 0 + helper(arr, i + 1, dp);
return dp[i] = Math.max(take, notTake);
}
}
Awesome 👏
very good man!
Thanks a lot Madhuraj ❤️❤️❤️
nice explanation❤
Thank you ❤️
MIK comes as a saviour.
Bro your explanations are exceptionally well crafted the finest I've come across on UA-cam
Means a lot to me.
Thank you so much 😇❤️🙏
That's a masterpiece
Tysm ❤️
Thank you. Explained well
Thanks a lot Nadim ❤️
Cleanest explanation😊
solved using recursion and memoization.............came here for bottom up...and u taught it so so well🔥🔥
i love your way of explanation and solutions.SO neat and clean.helps a lot. thank you.
You are most welcome 🙏😇
Thanks to your explanations from the previous videos, I was able to solve this before listening to your explanation :)
I really enjoy your explanations 🤩 The best explanation videos on internet ♥♥
Cold mornings🥶
MIK bhaiya ka POTD wala video ❤
Aur 1 cup chai ☕
Is all you need 😁
Thanks a lot bhaiya fr the super intuitive explanation❣
1 cup chai in the winter morning . What a perfect timing ❤️❤️😇
Hope we all meet soon and have a cup of tea together and do some gup shup 🙌🙏
Will soon plan with everyone.
@@codestorywithMIK Yes for sure a meetup will be great 🤩
you've got the best explanation skills❤. Thank you so much to be here on youtube.
You're so welcome! 🙏
just amazing
Thanks a lot ❤️❤️❤️
Great Explanation
Awesome explanation for recursion + memo. In bottom up, the indexing was confusing w.r.t 2 diagrams of array (dusrava ghar and ekva ghar)
I was able to solve it by all 3 methods thanks to your earlier videos!!
Great job! ❤️🙏
NICE SUPER EXCELLENT MOTIVATED
Best explanation
Bhaiya, what's the reason to have a array size of "n + 1" in bottom-up approach??
How can we find whether to have a "n" sized array or "n + 1" sized array ?
By the way, very well explained ❤
Explanation Level 🔥🔥🔥🔥
❤️❤️🙏🙏
god level explaination.....🙌🙌🙌Thankyou so much sir
Most welcome 😊
Awesome explanation
i'm crying literalllyy ; _ ; you are too gooodddddddd
🙏🙏 Means a lot
DSA DP series ❌ DP Web Series ✅
This channel is a Gem 💎
The man, the myth, the legend !!!
28:17 steal sjhould be nums[i] + nums[i-2], doesn't i-1 mean adjacent
Thanks !!
You the best!!
Means a lot 🙏😇❤️
best explanation!!!!
Glad it was helpful! ❤️🙏
Hey @codestorywithMIK I was able to define the state for this problem, but then I wasn't able to come up with pick t[i-2]+current or just pick t[i-1] . I want to be able to develop that ability how do I do that?
You are amazing bro ❤❤❤
Thankyou bhaiya❤
Thank you 😇❤️
The best and cleanest ❤
Java Implementation:
Rec+Memo
class Solution {
private int solve(int[] nums, int[] t, int idx) {
if(idx >= nums.length)
return 0;
if(t[idx] != -1)
return t[idx];
int take = nums[idx] + solve(nums,t,idx+2);
int notTake = solve(nums,t,idx+1);
return t[idx] = Math.max(take, notTake);
}
public int rob(int[] nums) {
int[] t = new int[nums.length+1];
Arrays.fill(t,-1);
return solve(nums,t,0);
}
}
Bottom Up:
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] t = new int[n+1];
//t[i] --> max profit obtained till house i
t[0]=0;
t[1]=nums[0];
for(int i=2; i
done
sir what will be the time complexity of the memiozation approach ?
In that case, it will be O(n) because we wont visit any stare more than once.
@@codestorywithMIK okay got it sir, Thank you!
understood! Thank you
Thank you 😇🙏
you the best
bro a humble request can you please upload a video of house robber III(337)on leetcode
Bhaiya ek basic sa doubt hai ki base case is something the largest or smallest valid case of a problem so iss case me agar i>=n hogaya tab to ghar hi exhaust ho jayega to wo ek valid case kaise hua?
Are you referring to line-5 at 15:02 ?
Yes bhaiya...sorry to tag time lapse
@035-harshitsingh7 No worries.
Yes it’s an invalid case that’s why we return 0 in that case
POTD DONE [21.1.24] ✅✅
sir cant we start from last index
Here after Aditya verma playlist
in pick no pick what ever the code is for no pick or skip is it always (i+1) or it varies if varies please let me know an example where it various
Always remember that, nopick means we are excluding/ignoring/not-taking that index and hence it will always be i+1
BUT,
“pick” can be tricky.
It can be i or i+1 or start from 0 again etc
Thanks alot mike you clear my doubts immediately even a paid tutor takes times
Thanks alot
@jagadeeshp1163 Happy to help 😇❤️🙏
why memset why not any other data structure?
[2,1,1,2] ispe recursion tree draw krke try kiya tha anybody? ans 4 aana chaiye but 3 h aara diagram se
rob({2, 1, 1, 2})
/ \
rob({1, 1, 2}) rob({1, 2})
/ \ / \
rob({2, 2}) rob({2}) rob({}) rob({})
/ \
rob({}) rob({})
I think tree diagram se bhai 4 aa Raha maximum. see the right side tree.
We took index= 0 (amount = 2)
And then we are left with {1, 2}
Now, we skip I and steal 2 (index 3)
Total = 4
31 mar 2024