House Robber III - Tree - Leetcode 337
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: leetcode.com/problems/house-r...
0:00 - Read the problem
1:45 - Drawing Explanation
13:55 - Coding Solution
leetcode 337
This question was identified as a google interview question from here: github.com/xizhengszhang/Leet...
#house #robber #python - Věda a technologie
🌲 Tree Playlist: czcams.com/video/OnSn2XEQ4MY/video.html
Out of all the leetcode solutions on CZcams, you write the cleanest, most understandable code. Please keep up the excellent work
Not everyone has the ability to teach brother you have it. keep enlightening us. !!
Love it ! Elegant and the way you write your code with few lines at the bottom , few lines in the middle like finishing a puzzle. It's beautiful.
your way of solving problem especially building from scratch and your explanation is very clear and good .please do more videos on most solved leetcode problems.
Thanks so much! Ur videos have been helped me a lot. #1 channel on my list for leetcode study. Looking forward to see more of your videos!
This playlist is absolute gold. Don't know what I will expect in DP and Graphs.
Im dying at the corresponding number of Macauley Culkins in your House Robber series thumbnails, its just *chefs kiss*
It is incredible how comprehensible and organized your explanations and solutions are. Thank you so much!
Very Nice and Simplified explanation . Really appreciate your work.
I really think whoever proposes this problem is definitely a genius! Such a problem with dfs, binary tree and dp, what a combination!
Beautifully explained. Thanks!
I just want to add a comment for people who might not understand thoroughly. We are not simply skipping child nodes and reaching grandchild nodes. The max() here means we are carried over the largest value of the subtree with the grandchild node as the root for each grant child root. That is amazing. Thank a ton
I feel that this problem requires the combination of Dynamic Programming and DFS (Recursion), and you explained this problem very clearly. Even though I am using Java and you are using Python, I followed your logic and did this problem correctly. Thank you very much for your fantastic teaching and explanation!
Thank you for the great explanation!
Great Explaination. Loved it. Have been watching your videos for the past 2 months. This explaination forced me to do away with my laziness and comment.
Dude, this is some rockstar level content really. I can’t tell how grateful I’m and how motivating these are! Thanks a lot!
Amazing, really helpful, thank you!!!
thank you so much bro. You gave an excellent explanation.
Great explanation!!!
Thanks! very great explanation!
Very nice, thanks
such clear explanation
I start watching your channel when it was at 90k and now it's 95k ,(in approx. 1 month) ..Congratulation
great explaination
I did it using bfs, borrowing from the solution to House Robber II
from collections import deque
class Solution:
def rob(self, root) -> int:
def bfs():
rob1, rob2 = 0, 0
queue = deque()
queue.append(root)
while queue:
n = 0
for i in range(len(queue)): # level order
node = queue.popleft()
n += node.val
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
temp = max(rob1 + n, rob2)
rob1 = rob2
rob2 = temp
return rob2
return bfs()
Are you fr? I thought I couldn't solve this problem until I saw your explanation. Thanks for making an impact 🙌
Thank you very much! This was really good
Very well explained!!! .
BEAUTIFUL SOLUTION
This channel is the real leetcode premium
Amazing solution
Bfs, store sum at each level and then just find max using alternate cells (0,2,4,...) (1,3,5,...). O(n) mem and O(n) time.
This is what I thought as well
This won't work for something like [2, 1, 3, null, 4]. Answer should be 7. This approach will return 6
@@alokesh985 nice one
Awesome content. can you cover some segment tree problems in future videos
Thanks!
I tried level order traversal and built an array list and then ran house robber 1 approach but it did not solve the edge cases.
I hope one day I would be able to solve the way you do it!.
Would you be able to explain what was your thought process to come to this solution
Thanks you sir! :-)
U a God
I was asked this question in an interview and I failed and I thought that it would use some complex data structure and algorithm, but your video proved me wrong! 😂 But honestly, thank you so much for explaining this!
What interview did you have?
@@shaksham.22 Rippling
This approach is giving TLE in C++
Here's the code
class Solution {
public:
pair help(TreeNode* root)
{
if(!root) return {0,0};
if(!root->left && !root->right) return{root->val,0};
return {root->val+help(root->left).second+help(root->right).second,(max(help(root->left).first,help(root->left).second)+max(help(root->right).first,help(root->right).second))};
}
int rob(TreeNode* root)
{
return max(help(root).first,help(root).second);
}
};
It'd be great if someone could help
I tried using House Robber I + BFS for this problem
one, two = 0, 0
queue = [root]
while queue ->
num = 0
for _ in queue ->
node = queue.popleft()
queue.push(node.left)
queue.push(node.right)
num += node.data
one, two = two, max(one + num, two)
return two
the most perfect ever.
Please can you increase the frequency i.e can you do more questions?
beautiful
OMG ! genius
what will be the time complexity and space complexity of this algo?
Smooth like Vaseline.
Will this solution be enough in an interview
recursion makes problems easy af
🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Nice thumbnail
what does leftPair[1] and rightPair[1] even mean? The left most left node at the end of the binary tree?
it represents the maximum score the robber can get if he decides not to rob the root node
one question: when should we build a new nested funtion?
when you wanna pass a parameter that isn't given by the parent function
@@jorgemejia1586 But why can't we just set an variable, why should use a function?
like we can just set n = 0 to change n
why should we do it like def dfs(n) to change n?
For this input [2,1,3,null,4] ans is given as 7. Isn't it 6
tree : 2
1 3
4
god right here people
Can we solve it using BFS ?
Can we do level order traversal on this
for a skewed tree, level order traversal might not work. eg. 4 - 1 - 2 - 3 . level order will retun max 6 (4+2). but the robber can rob 4 and 3 and make a profit of 7
bro i thought you could use bfs on this one
Picasso 🤏🤏
Is it possible to solve this in an interview without coming across it even once? 🧐
yeah
when a teacher unlocks his god-level mode 🤯
why cant you chose 4 and 100? They aren't directly connected. This is an ambigious question with no solution and you just wrote a solution of your own version of question.
Why are we helping the thief?
It did not pass for me. I copied it exactly but does not pass :(
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# return pair: [withroot, withoutroot]
def dfs(root):
if not root:
return [0, 0]
leftPair = dfs(root.left)
rightPair = dfs(root.left)
withRoot = root.val + leftPair[1] + rightPair[1]
withoutRoot = max(leftPair) + max(rightPair)
return [withRoot, withoutRoot]
return max(dfs(root))
rightPair = dfs(root.left) this should be
rightPair = dfs(root.right)
please start coding in c++
class Solution {
public:
map map ;
int rob(TreeNode* root) {
if(not root) return 0 ;
if(map.count(root)) return map[root] ;
int withoutRoot = rob(root->left) + rob(root->right) ;
int withRoot = root->val ;
if(root->left) withRoot += rob(root->left->left) + rob(root->left->right) ;
if(root->right) withRoot += rob(root->right->left) + rob(root->right->right) ;
return map[root] = max(withRoot,withoutRoot) ;
}
};
@@adityarathi3420 Hi , why is memoization needed ??? what is the repeated step here ?
@@shivanshgupta5657 without memoization i will getting tle on leetcode.
@@adityarathi3420 yeah I got the same but I used to think memoization is applied when we reapeatedly reach a given state in recursion. In this however we will traverse every node for once and there is no repeated state so why is there a need to memoize ? am I missing something ?
you are making it more complicated. You also draw too much and say tooooooo much. provide the idea first, then try to explain. This will make sense then. Otherwise, you are just trying to explain without giving how to do it and at last you tell this is the way you do it. That is not helping at all.
why is BFS not working here?
given below is my code:
if not root:
return root
q = deque([root])
res = []
while q:
val = []
for i in range(len(q)):
node = q.popleft()
val.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(val)
rob1, rob2 = 0, 0
for i in range(len(res)):
if not i % 2:
rob1 += sum(res[i])
else:
rob2 += sum(res[i])
return max(rob1, rob2)