🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

@AnnieBox

2 жыл бұрын

Q: we only need to get the max sum WITH split, and we already update it inside of the dfs, then why we still need to return the max sum WITHOUT split from the dfs?

@kippesolo8941

Жыл бұрын

i wonder how this works with negative values, shouldnt "leftMax = max(leftMax, 0)" turn any negative number into 0 ?

@kippesolo8941

Жыл бұрын

@@AnnieBox how do you think we update leftMax and rightMax then?

When I search for an explanation, yours would always be my first choice, even though I don't use python, the way you explain each problem is just informative and enlightening, thank you!

@shaikdiary

2 жыл бұрын

+1. I use Java, but i watch your videos for logical solution and then implement in java on my own (or watch other Java solution videos to refer the implementation details)

@hitarthdaxeshbhaikothari1688

2 жыл бұрын

Yes, same! I use C++ but always come for explanation here :)

@ShivamKumar-qv6em

2 жыл бұрын

@@hitarthdaxeshbhaikothari1688 same here bro .

@mingjuhe1514

2 жыл бұрын

+1 this is a very good channel.

@sagivalia5041

Жыл бұрын

I find it a great way to understand it by translating his Python code to the language I use

Very well explained! I love your videos so much. Your channel is my first resort when I am stuck with complex algorithms. Even the Leetcode solutions are not this simple to understand. Thank you so so much! :)

This is the best explanation for this problem I've ever seen. I struggled so much with wrapping my head around the solution in CTCI. Yours makes so much more sense, I wasn't even all the way through your explanation, but was still able to use what I learnt from it to code this up quickly on Leetcode. Thank you man, you're a legend!

can't believe that actually solved that many problem and upload the explanation to KZread :D . Currently, start my leetcode prac and found your channel here. Amazing work.

Spent so much time on this problem to understand the problem statement.. yours is by far the best explanation on what is expected of the problem and how to solve it as well. The idea of splits and why we should send 0 is very helpful to understand. Lots of appreciations! Keep up the good work! You are helping a lot!!

@Nick-kb2jc

2 жыл бұрын

Dude, same here. I hated this problem.

a version without the global variable res (it worked for me at least): class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: def dfs(root): if not root: return 0, float("-inf") left, wl = dfs(root.left) left = max(left,0) right, wr = dfs(root.right) right = max(right,0) res = max(wl, wr, root.val+left+right) return root.val+max(left,right) , res return dfs(root)[1]

@PhanNghia-fk5rv

2 ай бұрын

did u handle the case where root.val > root.val + max(left, right) ?

@aleksey3231

2 ай бұрын

gj man. The code is indeed concise and beautiful

Nice explanation . Very helpful . The way of explaining through diagram makes the things crystal clear .

Mate if it wasn't for your vids I'd be so lost. Was able to do this hard problem on my own today after studying your vids for months. I haven't tried it since 4 months ago but was easily able to come to the solution after learning your patterns. This was just a postorder traversal. Thanks

I've noticed you tend to do that list by reference trick for primitive values. Python also has built in way to do that, you can declare the variable normally, and then inside the DFS, do "nonlocal" res. def max_path_sum(root): res = root.val def dfs(node): nonlocal res if not node: return 0 etc.....

I am totally stunned by this solution. You are so amazing.

Here's using nonlocal and also not having to check leftMax and rightMax twice for 0 class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: res = root.val def traverse(node): if not node: return 0 leftMax = traverse(node.left) rightMax = traverse(node.right) nonlocal res res = max(res, node.val + leftMax + rightMax) return max(0, node.val + max(leftMax, rightMax)) traverse(root) return res

Your explanation is so brilliant and clear so that it seems like this is a medium or even easy problem instead of hard! Really appreciate your work and I really think Leetcode should use your solutions whenever possible!

Thank you so much for this explanation. I don't know who comes up with these Leetcode problems but this problem was so damn confusing. Leetcode doesn't provide enough example inputs/outputs for Hard problems like this. I had no idea what was defined as a "path" and it was so frustrating because I was running the solution code and still not understanding why I was getting certain values.

@zl7460

Жыл бұрын

Exactly. I coded a solution assuming 1 node is not 'non-empty', since there is no 'path'... Problem description is very unclear.

BRILLIANT explanation, thank you Neetcode!

Wow! You're the master! Thanks for sharing!

Highly underrated channel! Much Appreciated Content !

@NeetCode

2 жыл бұрын

Glad it's helpful!

Thank you so much for this brilliant explanation. One tiny remark: Perhaps using a "nonlocal res" in the dfs() function and saving the direct sum instead of a list might have been more clean.

@dongdongchen455

2 жыл бұрын

how to do that?

@zhengzuo5118

2 жыл бұрын

How to do that? I can’t use a single variable for res because it always gives an error

@sagarpotnis1215

2 жыл бұрын

@@dongdongchen455 in the dfs function at the top just define 'nonlocal res' at the top

Awesome explaination of the problem with the optimised solution approach 🔥🔥

Great explanation! may talk about time complexity too.

Lovely content btw, i can't believe how simple u make it

Thank you for the wonderful content. My question is why going with the array syntax for res, it would be simpler syntactically to use a normal variable. The Javascript equivalent, note that functions mutate global variables (wouldn't recommend it but it works): let res = 0 const dfs = (root) => { if (!root){ return 0 } let leftMax = dfs(root.left) let rightMax = dfs(root.right) leftMax = Math.max(0, leftMax) rightMax = Math.max(0, rightMax) res = Math.max(res, root.val + leftMax + rightMax) return root.val + Math.max(leftMax, rightMax) } const maxPathSum = (root) => { res = root.val dfs(root) return res };

@japarjarkynbyek8494

6 ай бұрын

Try to run exact code in Python. You get error because you gonna change that "res" is not defined in that sub function I guess or you cannot mutate global primitive value

requesting more interview problems, thank you as always

For some reason, I find it more intuitive to only use max() for selecting the largest choice, rather than also using it to coerce negatives to zero: def maxPathSum(self, root: Optional[TreeNode]) -> int: def maxLeg(root: Optional[TreeNode]) -> int: nonlocal max_path if not root: return 0 l = maxLeg(root.left) r = maxLeg(root.right) p = root.val max_leg = max(p, p + l, p + r) max_path = max(max_path, max_leg, p + l + r) return max_leg max_path = -1001 maxLeg(root) return max_path

Keep sharing new videos ! Your videos are awesome :)

nice and neat explanation!! 👍

BTW, you can directly plug in '0' as an option when returning from the recursive function. In that case, you only need two or three 'max()' operations, not four: class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: self.res = root.val def dfs(node): if not node: return 0 right = dfs(node.right) left = dfs(node.left) self.res = max(self.res, node.val + left + right) return max(node.val + max(left, right), 0) # Alternate return statement: # return max(node.val+left, node.val+right, 0) dfs(root) return self.res

explained so smoothly!!!👌👌👌

Thanks for making such great content for learning, I have one question "how much time you require to solve hard question like this ?"

Do you have a github link with your code solutions? Your explanations are amazing!

This one really confused me. Thanks so much for your explanation.

very clear! thank you!

Such a clean and clear explanation!

I actually solved this one on my one, granted its one of the easier hard problems (and my code ran pretty slow, beat 28%). However, I originally misinterpreted the question as find the max subtree, not path. Luckily it was literally one line of code difference between the two problems the way I solved it, but its a good reminder to make sure you really understand what is being asked.

Another banger of a solution. I was so close, yet so far :')

such an amazing video.

Best explanation. Downgraded the question to Medium level. Thank you!

You are just great!

U a God. I thought I had to implement dp somewhere, but glad I didn't! Thanks!

@edwardteach2

2 жыл бұрын

Python implementation: class Solution(object): def maxPathSum(self, root): """ :type root: TreeNode :rtype: int """ self.ans = float('-inf') def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) left = max(left, 0) right = max(right, 0) self.ans = max(self.ans, root.val + left + right) return root.val + max(left, right) dfs(root) return self.ans

Another way to conceptualise what constitutes a path is to only have those nodes or vertices in consideration that have at most 2 edges.

yeah there is no way i'm solving this in 45 minutes interview question ...

heyy quick confirmation question: I notice that the dfs function has return statement after we update res[0], but this very last value that's returned didn't get used, does it mean it's for the root to pass to its parent? (but since it's already the root, it won't pass it further, so we just ignore it? Thank uu!! really love ur videos!!

@NeetCode

3 жыл бұрын

Yup thats exactly correct! and thanks for the kind words

@monicawang8447

2 жыл бұрын

@@NeetCode Heyy NeetCode, I was doing this problem again and noticed that you used 'res' as an array whereas I just used it as a variable. However, when everything else stays the same, it gives scope error and I had to add "nonlocal res" in the dfs function. I'm confused that both methods are changing 'res' in the inner function, but why does your method not need "nonlocal"?

@johns3641

2 жыл бұрын

@@monicawang8447 You can modify lists, sets, dictionaries that are initiated outside of the function but you can't do that with strings/ints (which sounds like what you did at the end). Because you set res as an integer instead of a list, you have to add the words nonlocal for python to know that it has to modify the variable outside of the dfs function. Just a python quirk, hope that helps

@nachiket9857

Жыл бұрын

Returning the value of the actual root would assume that the path traverses through root, so it could be solution to a problem which has that constraint I believe (for anyone reading this later)

Great explanation! Thank you so much.

This is gold.

Amazing explanation ❤

good solution thank you

Awesome explanation. I solved but took some times and mistakes but what I learned is that if you don't solve problem on paper, don't code it. You are likely to go towards a dead end in 45 minute interview. Better solve it fully on the paper with all edge cases and then coding is like 5 minutes

Thank you very much!

thx!! But I have a question. Why we use the array to store the final result?

@wilsonwang8641

2 жыл бұрын

@Caleb Rigg explains this well below

How can be space complexity be O(h) we aren't using any extra memory ,are we?

@NeetCode

2 жыл бұрын

Good question, the memory comes from the recursion call stack.

@mohithadiyal6083

2 жыл бұрын

@@NeetCode thank you 😁

All leetcode problems should be like this

Great solution and video! Why does using a list for the res make modifying it within the recursive function easier?

@howheels

Жыл бұрын

It's not really "easier" but it avoids having to specify "nonlocal" inside the dfs function. IMHO using a list for res is not as intuitive, but you save a whopping 1 line of code.

def dfs(node): if not node: return 0, float("-inf") left, left_max = dfs(node.left) right, right_max = dfs(node.right) return max(node.val, node.val + max(left, right)), \ max(node.val, node.val + max(left, right, left + right), left_max, right_max) _, max_val = dfs(root) return max_val

I'm a little confused as to how the result gets updated to include conditions where you don't split. ie, we never really check for cases where we only take a path 1 way if that maxes sense

@beonthego8725

10 ай бұрын

The question says , the path does not need to pass through the root

general question, when analyzing trees, often you are calculating something recursively, is that considered overlapping subproblems or not? and are binary trees considered inherently optimal substructures? or not. thanks! btw love your videos and subbed!

@tejeshreddy6252

2 жыл бұрын

Hey, not sure if you still need the answer but here goes... Generally with a tree all nodes are unique so there are no sub-problems like in fibonacci series etc. In the latter case, we have non-unique nodes such as 2, 3, 5 which we have to traverse again to get to the bigger solution

Thanks man

Excellent explanation thanks! Just curios why 'res' needs to be an array if you are only using the 0 index, is this a python thing?

@michaelmarchese5865

4 ай бұрын

In python, you can read a variable from a higher scope (meaning from outside the function) without a problem. But if you try to modify that variable, it'll think you are trying to create a new local variable, leading to exceptions/bugs. To modify the preexisting variable from outside the function, you need to use the nonlocal keyword. For some reason, neetcode guy decided to avoid nonlocal in favor of a hack. He uses a list for his higher-scoped variable because then he can store the actual value inside of it and modify that rather than the list itself, avoiding the issues I mentioned above. But don't do this. Use nonlocal. In addition to nonlocal, there is a global keyward that does the same but for globals. Neetcode refers to res as a global variable, but it's not. It belongs to the outer function.

Shouldn't we return max (dfs(root), res[0]) as the result (it could be the case that either left or right path is negative)?

@beonthego8725

10 ай бұрын

The question says , the path does not need to pass through the root.

@arnobpl

Ай бұрын

"The path does not need to pass through the root" sounds like a flexibility but not a constrain. Otherwise, it should say, "the path must not pass through the root." I am confused with the same thing. I tested the code in both ways and both pass all the test cases.

@arnobpl

Ай бұрын

Anyway, I understood why max(dfs(root), res[0]) is not needed. It is nothing related to "the path does not need to pass through the root". In fact, in Example 1, the max path does pass through the root (2+1+3=6). It is because: think about the dfs call when root.val is the actual root of the tree. In line 22, both leftMax and rightMax are non-zeros due to line 16-17, so we are also considering either left or right path being negative. That is why we do not need max(dfs(root), res[0]). That is redundant.

In other languages you can use static variable inside the function instead of global variable

@colin398

2 жыл бұрын

or an instance variable, anything works either way its not actually global just outsidd the scope of the inner method

I just paused the video to write a comment here to say that I feel like I've watched so much of your content, at this point it just feels like I'm talking to you lol.

@farazahmed7

2 жыл бұрын

koi company nikaali wikaali?

I was expecting an implementation kinda similar to the house robber III prob lem

Hi, my concern is "How am i supposed to come with such logics when I'm given such problems in any interview?". If you got anything other than "Through practice !" , then I would love to know ; )

In case this helps things 'click' for anyone, I realized this is really similar to Maximum Subarray. In fact if the tree had no splits (were just a linked list) it would be the same algo. But since the tree _can_ split, it just means we have _two_ running sums to look at instead of one.

Amazed.

Could you give the time complexity and space complexity ?

What is all the values are negatives?

This problem should be marked "Easy with Leetcode video" lol. Thank you for making things so comprehensive !

Great video, is there a github location where I can find all your codes?

@TechOnScreen

2 жыл бұрын

yes.. navigate to this url github.com/neetcode-gh/leetcode

thanks

You should redo this problem in 2024. Some mistakes I found - you mention adding when you were talking about `max()`, you don't have to use an array for `res` and then just return the first element, it could be a variable. You don't even need that value. You can just do `return dfs(root)`

I am still confused about line 24. Can anyone explain to me how it works?

What's the best way to solve without using the global variable?

@Saralcfc

2 жыл бұрын

Return tuple of values (max_path_without_splitting, max_path_with_splitting)

What is the time complexity ?

Ok let's write some more neetcode if you says so

thank you! Hope this one like and a comment support the channel!

God's work

I don't understand, why do you need to make res into a list?

so why does the list for res allow it to be changed in the function?

@minyoungan9515

2 жыл бұрын

@Nolan were you able to figure it out?

@avenged7ex

2 жыл бұрын

@@minyoungan9515 In Python, lists are a mutable object, while primitive type assignments are not (You can think about this like saying lists are always passed by reference, and objects like integers are not). So by passing a list containing a value, the reference to the list isn't lost, yet we're able to change the value inside of it. Another work-around would be to declare the result within the object, where it can be referenced using self.res . Another choice would be to define res outside of the dfs() function, and then define it again within the function using the nonlocal keyword.

@minyoungan9515

2 жыл бұрын

@@avenged7ex Thanks for the explanation :) That makes sense

3:17 "this(implying 2+1+3+5) is obviously the maximum we can create" BUT NO the right sub tree 4+3+5 =12 is the max sum path.

why do we need computations for path sum with split then? someone please enlighten me on this 😮‍💨

u have a gift my guy

Here is the cpp version with code explanation: int res = INT_MIN; int maxPathSum(TreeNode* root) { dfs(root); return res; } // return max value through current node // max value either comes from: // 1. split at current node; // 2. split through parent node, max value current node could provide. int dfs(TreeNode *node) { if (!node) { return 0; } int left = dfs(node->left); left = max(left, 0); int right = dfs(node->right); right = max(right, 0); // split at current node. res = max(res, node->val + left + right); // not split to parent level, max value current node could provide return node->val + max(left, right); }

you can just use `self.res` instead of [res] to modify the value globally. using the properties of a list to achieve this might be seen as a little hacky by the interviewer.

Can someone explain the concept of adding 0 while updating leftMax and rightMax?

@SandeepKumar16

2 жыл бұрын

The idea behind comparing with 0 is - We don't want to add up negative numbers in the path. Because that would decrease the sum. So we compare with 0. If leftMax is negative, max(leftMax, 0) with give 0. Adding 0 to the result will not effect the result.

What if all the nodes are negative?

@avenged7ex

2 жыл бұрын

This is handled by always including the current node's value in the max() calls. The result variable would be assigned to the largest individual node value in that case, as it is always included in any max() call.

can anyone tell me time and space complexicity please?

this is kinda like house robber 3

Why is your `res = [root.val]` as opposed to `res = root.val`? Why make it a list?

Can anyone provide O(n^2) solution to this problem ?

leftMax is a node, how come `max(leftMax,0)` returns a value?

@avenged7ex

2 жыл бұрын

LeftMax isn't a node, it is the returned value from the dfs() call which is passed the node as a parameter. The code runs recursively until the node is determined to be null (meaning we've reached the end of the tree) and return 0. At the bottom of the recursion stack we calculate the max values between this new 0 value and the value of the leaf node, and return a maximum value (see how we just returned the max? this is the integer value leftNode is assigned). Now the recursion calls begin to finish, all-the-while passing the previous maximums to the leftMax and rightMax variables.

can you guys explain why the res is list instead of a simple variable

@avenged7ex

2 жыл бұрын

simple variables are immutable (think of this as passed by value), whereas, lists are mutable (passed by reference). In order to change the value of the result, he's wrapped it in a list so that the reference to the answer is never lost, while allowing him to alter the value within the lists contents. Another work around would be to declare the res variable as an instance of the Solution class (self.res). Or by declaring it outside the dfs() function, and also within it using the keyword nonlocal (i.e. nonlocal res).

@Ifeelphat

2 жыл бұрын

@@avenged7ex interesting so was the list used to improve performance?

@avenged7ex

2 жыл бұрын

@@Ifeelphat no, it was used to increase readability

@saugatkarki3169

Жыл бұрын

it shows UnboundLocalError when a simple variable is used instead of a list. that's what it did for me.

@liamsism

Жыл бұрын

@@avenged7ex tuples are immutable too but it works with them.

why make the global variable - res - an array with one item? why not just set the value to the item itself? we never push or append anything else to it. just curious, thank you for all that you've done.

@VipulDessaiBadGAMERbaD

2 жыл бұрын

it works even if its not used as array, actually it should be just a simple variable

Can anyone explain why he used res[0], why not just use res, not make it a list since the start declaration ?

@shivanshgupta5657

Ай бұрын

global variable declaration i think. ChatGPT suggested this.

why he have used a list for the res , why not just a integer? can anyone make me understand please!

@angelinazhou667

Ай бұрын

Using a list for the res allows us to update the result within the helper function. If res was instead simply a variable that stores an integer, when we try to update it within the helper function, it will create a new variable called res local to the helper function. We use a list to get around this problem or you could alternatively use a variable with the nonlocal keyword

@sankhadip_roy

Ай бұрын

@@angelinazhou667 yes Or can use a class variable using self

I first tried to solve the question without considering the single path and later I realized it is not allowed

This problem was something

could someone explain how to do this without the global variable

@Rob-147

Жыл бұрын

I did it using a pair of in c++. code is below /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: pair dfs(TreeNode* root) { if (!root) return make_pair(0,INT_MIN); pair left = dfs(root->left); pair right = dfs(root->right); int currPath = root->val + max(max(left.first,0), max(right.first,0)); int currMaxPath = root->val + max(left.first,0) + max(right.first,0); int maxPath = max(max(left.second,right.second), currMaxPath); return make_pair(currPath, maxPath); } public: int maxPathSum(TreeNode* root) { pair result = dfs(root); return result.second; } };

why global would be considered as cheating?

I coded a solution assuming 1 node is not 'non-empty', since there is no 'path'... Problem description is very unclear.

Dude please make videos on path sum 2, 3