House Robber III - Tree - Leetcode 337

[@NeetCode]

🌲 Tree Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@alokesh985]

Out of all the leetcode solutions on KZbin, you write the cleanest, most understandable code. Please keep up the excellent work

[@prithulbahukhandi1714]

Not everyone has the ability to teach brother you have it. keep enlightening us. !!

[@tonymontana9221]

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

[@ArvindKonda]

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.

[@raghavendharreddydarpally2125]

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.

[@lizgarcia4626]

It is incredible how comprehensible and organized your explanations and solutions are. Thank you so much!

[@boopeshshanmugam3436]

There is so much work behind the video of choosing the right test cases to give the explanations in the best way. Thanks for your efforts. You rock !

[@VY-zt3ph]

This playlist is absolute gold. Don't know what I will expect in DP and Graphs.

[@youlihanshu]

I really think whoever proposes this problem is definitely a genius! Such a problem with dfs, binary tree and dp, what a combination!

[@eyou2813]

Im dying at the corresponding number of Macauley Culkins in your House Robber series thumbnails, its just *chefs kiss*

[@shuhaoliang144]

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!

[@aritralahiri8321]

Very Nice and Simplified explanation . Really appreciate your work.

[@ashishm8850]

Beautifully explained. Thanks!

[@lonen3rd]

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()

[@sushantrocks]

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.

[@prathamj2215]

This is what I thought as well

[@alokesh985]

This won't work for something like [2, 1, 3, null, 4]. Answer should be 7. This approach will return 6

[@sushantrocks]

@@alokesh985 nice one

[@aayush9080]

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.

[@dhaanaanjaay]

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

[@yicheng7712]

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!

[@shivambaghel9668]

I start watching your channel when it was at 90k and now it's 95k ,(in approx. 1 month) ..Congratulation

[@MsSkip60]

Dude, this is some rockstar level content really. I can’t tell how grateful I’m and how motivating these are! Thanks a lot!

[@arenmkhoyan]

Very nice, thanks

[@SairamDasari2000]

Are you fr? I thought I couldn't solve this problem until I saw your explanation. Thanks for making an impact 🙌

[@thanirmalai]

Amazing solution

[@begula_chan]

Thank you very much! This was really good

[@anthonyuccello1458]

This channel is the real leetcode premium

[@RobinHistoryMystery]

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

[@kvtys]

not enough circling at 8:00, failed to understand

[@skylyyun]

Thanks! very great explanation!

[@amitarya4894]

Thank you

[@HarshaVardhan-pj5gp]

You are just amazing 😭❤️

[@zacyou4220]

what will be the time complexity and space complexity of this algo?

[@___vandanagupta___]

Very well explained!!! .

[@ladanafar5917]

Please can you increase the frequency i.e can you do more questions?

[@ananya___1625]

Great explanation!!!

[@BarneyBing883]

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!

[@shaksham.22]

What interview did you have?

[@BarneyBing883]

@@shaksham.22 Rippling

[@ambarishdashora5440]

thank you so much bro. You gave an excellent explanation.

[@anshhchaturvedi1155]

This approach is giving TLE in C++

[@anshhchaturvedi1155]

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

[@tarunsahu1366]

@@anshhchaturvedi1155 class Solution { public: vector func(TreeNode* root){ if(root == NULL) return {0, 0}; vector leftPair = func(root->left); vector rightPair = func(root->right); int withRoot = root->val + leftPair[1] + rightPair[1]; int withoutRoot = max(leftPair[0], leftPair[1]) + max(rightPair[0], rightPair[1]); return {withRoot, withoutRoot}; } int rob(TreeNode* root) { vector result = func(root); return max(result[0], result[1]); } };

[@ritikkhatri]

such clear explanation

[@yinglll7411]

Thank you for the great explanation!

[@s.z.7938]

Amazing, really helpful, thank you!!!

[@aditijain2448]

Will this solution be enough in an interview

[@hoanganhtu9090]

great explaination

[@edwardteach2]

U a God

[@annoyingorange90]

BEAUTIFUL SOLUTION

[@danielsun716]

one question: when should we build a new nested funtion?

[@jorgemejia1586]

when you wanna pass a parameter that isn't given by the parent function

[@danielsun716]

@@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?

[@SmoothCode]

what does leftPair[1] and rightPair[1] even mean? The left most left node at the end of the binary tree?

[@rohithv63]

it represents the maximum score the robber can get if he decides not to rob the root node

[@nikhilchauhan5837]

Awesome content. can you cover some segment tree problems in future videos

[@andreytamelo1183]

Thanks!

[@midhileshmomidi3120]

For this input [2,1,3,null,4] ans is given as 7. Isn't it 6 tree : 2 1 3 4

[@binit1992]

Can we solve it using BFS ?

[@ajinkya-wasnik]

beautiful

[@sangamsamdarshi4634]

recursion makes problems easy af

[@midhileshmomidi3120]

Can we do level order traversal on this

[@sindhu5840]

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

[@joydeeprony89]

Smooth like Vaseline.

[@shaharrefaelshoshany9442]

the most perfect ever.

[@adityarathi3420]

Thanks you sir! :-)

[@asdfasyakitori8514]

Nice thumbnail

[@kwaminaessuahmensah8920]

god right here people

[@whatuphere]

Prabhu to the rescue!! _/\_

[@PoojaMehta271]

Is it possible to solve this in an interview without coming across it even once? 🧐

[@CertifiedDeadMemes]

yeah

[@laplacesdemon8140]

OMG ! genius

[@jorgemejia1586]

bro i thought you could use bfs on this one

[@sourav_ghosh]

Picasso 🤏🤏

[@skmdmobinulislam3904]

when a teacher unlocks his god-level mode 🤯

[@dhiwakarna8509]

Why are we helping the thief?

[@coldstone87]

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.

[@shadowsw8020]

'The thief realized it forms a binary tree' wtf is this shit lmao

[@nikhilgoyal007]

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))

[@amberfatima2777]

rightPair = dfs(root.left) this should be rightPair = dfs(root.right)

[@WowPlusWow]

🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@alishan9354]

please start coding in c++

[@adityarathi3420]

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

[@shivansh-gup]

@@adityarathi3420 Hi , why is memoization needed ??? what is the repeated step here ?

[@adityarathi3420]

@@shivansh-gup without memoization i will getting tle on leetcode.

[@shivansh-gup]

@@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 ?

[@officialnepalcricket]

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.

[@akashdey5637]

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)

[@salahabdelrahman7820]

Great Explaination