LeetCode 198. House Robber (Algorithm Explained)
Vložit
- čas přidán 20. 12. 2019
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering - Věda a technologie
yo you should have kept the robber mask while doing the question
This in old and I don't know if you ever read your subscribers comments, but I have to tell you one amazing thing about you. You have an incredible talent to explain complicated things in a very simple way. Yet, there is an extra impressive feature on your methodology of explaining things. You explain them really fast. Normally, one expect to make it more difficult to follow. But it is the other way around with your videos. You explains things very fast *AND* make them easy to understand. I don't think you even realize this. It is a bit antagonist, how can you explain it so well and so fast? But, man it works great. Thanks for posting these solutions with fast and easy explanations.
Explaining the template for dynamic programming did helped me.
Hi Nick, can you create a path or a map for beginners to follow which algorithm /data structure should they learn first and what problems should they do first.
Finally i understood this problem! Thank you... Also the fact that you used an array instead of a variable to show the progression of the maxvalue helped to understand
Thanks for the video. Here is slightly modified/improvised code:
int dp[] = new int[nums.length];
dp[0] = nums[0]; dp[1] = Math.max(dp[0], nums[1]);
for(int i=2; i
However, this solution will cause ArrayIndexOutofBounds unless you put another if(nums.length == 1) return dp[1].
I think apart from Fibonacci, this is the first time I truly understood a DP problem, even though its considered Easy. Thank you Nick, You explain really really well!
The template is really helpful! Very clear explanation again!
You lost me from 8:47 to 9:52 and sadly that the most important part :(
you really have a gift for this. i've been struggling to understand this when all i had to do was watch a couple of your videos to get it. THANK YOUUUUU
Great explanation. I like how you made clear what the template was for a dp problem.
Hello Nick. You explained this very nicely. Could you please make a playlist exclusively for Dynamic Programming problems? That would be extremely helpful. Thanks.
I find it easier to solve the problems after understanding a task via a decision tree. However after building out the decision tree and seeing that max_money_stealable is dependent on amount of money the robber has stolen so far, it became pretty difficult to move forward with.
For those who have MASTERED DP, this is probably an easy problem. For those that are still looking for easily digestible/understandable material on this topic called "Dynamic Programming", it's not easy.
11:00 There should be 4 elements. On line 5 you declared nums.length + 1 so [1,2] should be of array size of 3 and since array is zero based it goes from 0th index to 3rd which is total of 4 spaces.
You are a good sarcastic comedian
Nick I dont usually comment but this was a really good video. I’ve seen videos before about dynamic programming but they all made it seemed like this really advanced topic for no reason. When its just storing values in an array. Please make more videos just explaining each category of problems in simple terms this video was really helpful. 👍
Great explanation. You save my day bro
Did you ever end up doing that video on the main types of problems and how to spot them?
Thnx man ! It helped a lot :)
Could have used Kadane's Algorithm to do this in O(1) space :) with the same runtime
if (nums.Length == 0) return 0;
if (nums.Length < 2 ) return nums[0];
int ans = Math.Max(nums[0], nums[1]);
int a = nums[0];
for (int i = 2; i < nums.Length; i++)
{
var temp = Math.Max(ans, a + nums[i]);
a = ans;
ans = temp;
}
return ans;
^^ for reference if anyone was wondering (C#) implementation
Hey Nick I would like to solve all the problem you taught , is there any path in which I should do the questions ?
Thanks Nick!!
Can you please explain why the templet always set as int dp[] = new int [nums.length + 1]? What does mean to add 1? I still don't understand.
dude i'm literally only applying for SWE internship as a college junior and most of my OAs had dynamic programming. I'm not even joking.
Hey nick if you did a video on dynamic programming where you are explains types of dynamic programming question. Please send the link. I would like to watch.
immaculate explanation
Great explanation
Hello Nick,
I wish I am very good at solving coding problems without looking at the solutions. What are your advice?
Dude you are awesome!
what's up with the camera quality nick.. when you used your macbook the camera quality was better
Great understandable explanation, As we need only last two values, we can just maintain two variables and get the answer..that way space complexity would be O(1)..
Edit.: For those who missed it in video.!
mentioned in the video
@@NickWhite guess i skipped over that part..😅
"Not your morals" lmaoooooooo
Happy Holidays Nick. I saw in your previous videos that you used a mac, and now you are using windows. Any particular reason why you switched?
I bought a gaming PC and it’s pretty good for live streaming so I’m just messing around with it atm Happy holidays to you as well!
Hey Nick,
Just curious why we need an array "dp" when we already know that last element is going to be the result. Can we simply have 2 variables one to store prev-result and another for fina-result and do the same thing. Help me if I am missing anything...
func rob(_ nums: [Int]) -> Int {
guard nums.count > 0 else { return 0 }
var prevResult: Int = 0
var result: Int = nums[0]
for i in 1..
You cracked me up lol.
Great job
Good one, can you make video for dp
That thumbnail though😈😈
It helps , thanks.
love you man
Think again buster!
man you are very fast!
Think again buster! LMAO!
I still didn't see how the code covered that edge case of jumping two houses and grab the third, even though your code passed the edge use cases...
EDIT: Did a table test an got it:
dp [0, 40, 40, 44, 50]
40, 2, 4, 10
Thanks
Upvoting just because of that thumbnail xD
The rap king!
This is not memoization. This is tabulation, a bottom up approach.
Yes, thanks for saying that... I pretty much broke my head thinking of how it would be a memoization
How about this,
public int rob(int[] nums) {
if(nums.length>1){
nums[1]=Math.max(nums[0],nums[1]);
}
for (int i = 2; i < nums.length; i++) {
nums[i]=Math.max(nums[i]+nums[i-2],nums[i-1]);
}
return nums[nums.length-1];
}
0:45 WideHard
It can be one of two options. 1+3+..... +till the end or 2+4 +....+till the end since they can't be negative
Not necessarily. If two very large numbers are 5 indexes away from one another, they can be combined e.g.:
1, 100, 1, 1, 1, 1, 100, 1
Your method would return a max of 103 where the maximum is actually 201.
every time he says its the easiest problem i m like that isnt true that's why i am watching your video
Well now it is medium :)
u deserve a like for that mask
wheres the study guide
"Hello guys it's Nick White chushdskfjdksjfksjfks INFORMATION ksjdfkdj House Robber ". hHhahaha jk
Boom!😆
You lost me from 00:00 - 13:25 😁 I’m joking I’m just watching because I want to learn.
This is helpful even if you aren't using java
Boom
17
This is now under Medium category
bro is in 8k