Maximum Difference Between Node and Ancestor | Brute Force | Optimal | Google | Leetcode 1026
Vložit
- čas přidán 7. 12. 2022
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 16th Video on our playlist "Binary Tree : Popular Interview Problems".In this video we will try to understand a very good Binary Tree Problem - "Maximum Difference Between Node and Ancestor" ( Leetcode 1026 )
Problem Name : Maximum Difference Between Node and Ancestor
Company Tags : Google, Microsoft, Amazon
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/maximum...
GfG Link : www.geeksforgeeks.org/problem...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach Summary (Brute Force) - Pick every node and find it's absolute difference with all its ancestors. Update max diff during the journey. Do this for every node and its ancestors.
Approach Summary (Optimal Approach) - The key function is maxAncestorDiff, which initializes minimum and maximum values and then calls the recursive function findMaxDiff to compute the maximum difference between any two nodes in the binary tree. The findMaxDiff function traverses the tree recursively, updating the minimum and maximum values encountered along the way, and computes the maximum difference for each subtree. The final result is the maximum difference obtained across all subtrees, and it represents the maximum absolute difference between any two nodes in the given binary tree.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Timelines
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear
Liking the video before watching, because I know this will be quality content.❤
You made my day Pranav ❤️❤️❤️
Thanks a lot
9 views 7 likes :)
❤️😇
My reaction is also same ❤ nothing diffrence
This guy is literally a L.E.G.E.N.D
I believe at this point, you are one of the best tutors on CZcams for coding problems
After your explanation, I stopped and went to code myself and did it
Thanks a lot ❤️❤️❤️
i don't know why you are so underrated man(maybe bcoz all your audience is genuine not like "the lazy brats who subscribes a channel after adrenline hit and some madass who wants small videos to understand a concept"), but you are doing very well and thanks for beautiful content.
It means a lot to me.
Thank you for the trust in my channel 🙏🙏❤️❤️
And maybe they don't want to share this hidden channel with others ,because they know, it could be the game changer for them 🙈
I always had this same thought. How can a channel like this is underrated. I mentioned this before also that there can be many reasons :
1. He never asks or posts on any platform asking people to subscribe or like. He just posts link to his videos in Instagram, Fb etc
2. Till now, I have never seen even a single video where he sponsored any other paid platform.
3. In one of his videos, he mentioned that he got offers for promoting some other paid platforms, he denied them.
4. I think all he cares is to share his knowledge as much as he can.
5. Your point - People today don't want to watch long detailed videos. These days , people just want solution to maintain streak on leetcode, code forces etc.
6. @jatakchatterjee1459 also can be one of the reasons
I always wonder the same thing.
💯
I'm your daily viewer keep it up
Thanks a lot Manish ❤️❤️❤️
youbare superb ! ❤ap bruteforce fir optimal solution batate ho ye best lagta hai aur apka videos mujhe aur clarity deta hai
thank you for u r amazing content !
Thanks a lot ❤️❤️❤️❤️❤️
By far the best explanation. Thanks for sharing the Brute Force also😊
excellent explanation bro..
Best teacher so far
Bhai agar ese hi brute force har video mein explain krdo toh kya baat!!!! question bilkul dimag mein baith jata hai good work
Thank you 😇❤️🙏
The optimal approach was 🔥🔥
Others teach solution....u teach how to build a solution.
Thanks ❤❤
love love love love lovvvvvvvvvvvveeeeeeeeeeeee u bhaiaya 🥰🥰🥰🥰
Thanks a lot bhaiya 🔥❤
really good explanation! brute to optimal explanation really made sense. At no point it felt that we are doing something out of the box. You really navigated us through the solution smoothly.
Explanation with inuitition🔥🔥
Bro, You are providing quality & intuitive Solution.
Thanks Keep Posting & Growing
Thanks a lot Sanjeeb ❤️❤️❤️
Binge watching your entire playlist. You are a legend
bhai sahab bahut garda smjhaya h apne .
awesome
Did on my own using brute force ....came to see optimal approach
Great Explanation !!❤😍
did it on my own .. thanks to you I can solve these problems now
Glad to hear that 😇🙏
nice video yaar genuine explaination
Thanks a lot Gautam ❤️❤️❤️
The most underrated DSA teacher❤
Thank you 😇❤️🙏
great explanation as always
Thank you 😇🙏
Itna acha kaise parhate ho bhai 🔥🔥
bhaiaya ek baar next ya kisi or video mai thoda sa * pointer k baare mai aap thoda smjha dena , i always gets confused about it
reach++ bhai
Thanks a lotttt ❤️❤️❤️
Yes this guy really deserves ++
best explanation on YT so far❤
Means a lot 🙏🙏❤️❤️
Excellent Explanation Sir!!
Thanks Yash ❤️
hi, The Time Complexity for DFS is O(V+E) can we apply the same here?
Awesome explanation . Your teaching way is Gem in Stone
Thanks a ton 😇🙏
@@codestorywithMIK Currently I am working in CItrix R&D as staff Software Engineer. I was mostly in SDET profile. I want to apply in fang company. Around 450 questions I solved in leetcode. But I don’t how to get confidence for my experience
Really you nailed it bhaiya✨️✨️
Thank you so so much Uday ❤️❤️❤️
Nice explanation !!!!😍😍
Thank you so much Varun ❤️❤️❤️
sir what topics we should concentrate more sir
🔥
Sir mai apka purna fan hu 🥰 ek face wali video please
🔥🔥🔥
legend.
Thanks a lot 😇❤️
like leetcode try to gfg pot also sir
"MAIN DIRECT APPROCH NAHI BATAYUUNGA, MAIN STORY BATAYUNGA"
always wait for this dialogue 😁✌🏻
Thank you 😇❤️🙏
bhaiya any suggestion to improve recursion thinkimg
❤
Thank you 😇❤️🙏
thanks to you bhaiya
Dammnnnn🤩
Thanks a lot Shashwat ❤️❤️
Bhaiya Aaj gfg podt ka video upload kar dijiye
It helps a lot.
Hi there,
Actually I couldn't get time today for GFG Potd. But let me share here the intuition with full detail which help you to write the code on your own :
Here's the intuition behind the solution:
Greedy Approach: The solution uses a greedy approach to iteratively build the result string (result). The goal is to make the most significant digits as small as possible.
-> Iterative Digit Selection: For each digit in the input string S, we iterate through the digits and make decisions based on the following conditions:
If the current digit is smaller than the digit at the back of the result string, and there are still digits to remove (k > 0), we remove digits from the back of the result until the condition is not satisfied.
After this process, we append the current digit to the result string.
-> Remove Remaining Digits: After processing all digits in S, there might still be some digits left to remove (k > 0). In this case, we remove the remaining digits from the back of the result string.
-> Remove Leading Zeros: Finally, we remove any leading zeros from the result string.
Let me share a dry run for an example :
Example: S = "1432219", k = 3
Initial state:
result = "", k = 3
Processing digits:
For "1": Append "1" to result.
For "4": Remove "1" (from the back of result) and append "4".
For "3": Remove "4" (from the back of result) and append "3".
For "2": Remove "3" (from the back of result) and append "2".
For "2": Remove "2" (from the back of result) and append "2".
For "1": Append "1" to result.
For "9": Append "9" to result.
Removing remaining digits:
Since k = 0 and all digits are processed, no further removal is needed.
Result:
result = "12219"
Removing leading zeros:
The final result is "12219", which is the smallest number obtained by removing 3 digits from the original string.
I hope this helps.
Here is the C++ code for above :
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Stack/Remove_K_Digits.cpp
Thank you 😃❤
When we return from the left subtree, i. e after
int l = findMaxDiff(root->left, minV, maxV); (in the optimal solution)
Aren't the values of minV and maxV different when going into the right subtree?
What am i missing?
No actually, if you notice the minV and maxV are local to every recursion call.
i.e. when you are at root 8 (the maxV = 8, minV = 8),
maxV and minV are passed by copy (and not by reference) to further recursive call . So when the recursion comes back to 8, the minV and maxV will be (the maxV = 8, minV = 8), which was at that time when you were at root (8).
This is one of the things which always haunted me in Recursion. But after doing dry runs, I finally now understand how recursion flow works.
@@souravjoshi2293Aight Thankss
Waiting for the gfg solution bhai!
Hi there,
Actually I couldn't get time today for GFG Potd. But let me share here the intuition with full detail which help you to write the code on your own :
Here's the intuition behind the solution:
Greedy Approach: The solution uses a greedy approach to iteratively build the result string (result). The goal is to make the most significant digits as small as possible.
-> Iterative Digit Selection: For each digit in the input string S, we iterate through the digits and make decisions based on the following conditions:
If the current digit is smaller than the digit at the back of the result string, and there are still digits to remove (k > 0), we remove digits from the back of the result until the condition is not satisfied.
After this process, we append the current digit to the result string.
-> Remove Remaining Digits: After processing all digits in S, there might still be some digits left to remove (k > 0). In this case, we remove the remaining digits from the back of the result string.
-> Remove Leading Zeros: Finally, we remove any leading zeros from the result string.
Let me share a dry run for an example :
Example: S = "1432219", k = 3
Initial state:
result = "", k = 3
Processing digits:
For "1": Append "1" to result.
For "4": Remove "1" (from the back of result) and append "4".
For "3": Remove "4" (from the back of result) and append "3".
For "2": Remove "3" (from the back of result) and append "2".
For "2": Remove "2" (from the back of result) and append "2".
For "1": Append "1" to result.
For "9": Append "9" to result.
Removing remaining digits:
Since k = 0 and all digits are processed, no further removal is needed.
Result:
result = "12219"
Removing leading zeros:
The final result is "12219", which is the smallest number obtained by removing 3 digits from the original string.
I hope this helps.
Here is the C++ code for above :
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Stack/Remove_K_Digits.cpp
Thank you 😃❤
Are bhai bohot succes milega yr apko.
Dedication in you seems to have no bound. Chalte rehna bss rukna nahi. View rate slowly badhega, but badhega zaroor. All the best!!
@mr_stranger3867 Means a lot 🙏🙏
Today’s
GFG POTD - czcams.com/video/2fA9-uhVliY/video.htmlsi=z8egnJ00xhFiDyjX
Leetcode POTD - czcams.com/video/oSSMo0PCQts/video.htmlsi=Rjl0HcG11HhjQ4qQ
Thank you ❤️❤️
second approch mane socha tha 🥲
Bhaiya java me bhi code Kiya Karu bhaiya
Sure. As of now I always add Java code in the GitHub link in the description. Hope that helps
Time complexity for this code will be O(n) where n is the no of nodes because we are travelling all the path possible
Space complexity (recursive call stack) if we look closely at max only no of node equal to height of tree is
going to the stack so SC will be O(height of tree)
Hope it help for upcoming viewers 😊😊
Awesome.
Thanks a lot Uday ❤️❤️❤️
i am not getting interest to see examples and kearning my solution tab always watching yt solutions any suggestions sir to improve sir
Why this LeetCode official recursive solution is not working in C++?
class Solution
{
public:
int result = 0;
void findMaxDiff(TreeNode *root, int currMax, int currMin)
{
if (root == NULL)
{
return;
}
int possibleMaxDiff = max(abs(currMax - root->val), abs(currMin - root->val));
result = max(result, possibleMaxDiff);
currMax = max(currMax, root->val);
currMin = max(currMin, root->val);
findMaxDiff(root->left, currMax, currMin);
findMaxDiff(root->right, currMax, currMin);
return;
}
int maxAncestorDiff(TreeNode *root)
{
if (root == NULL)
{
return 0;
}
result = 0;
findMaxDiff(root, root->val, root->val);
return result;
}
};
I think I got it :
currMax = max(currMax, root->val);
currMin = max(currMin, root->val);
//Here , it should be min instead of max
@@codestorywithMIK Thanks for correcting my mistake.
Can you please start explaining POTDs of GFG?
I am glad I could help.
And regarding POTDs, i was not planning then due to crunch of time. But I will plan them soon too. Because I noticed the qns there are good.
Thanks for asking Priyanshu.
@@codestorywithMIK I really like your every problem explanation.
Okay, Thank you!
Means a lot ❤️
Class solution {
Public int max Ancestor Diff(Treenode root){
return find(root, root. Value,root. Val)
};
Private int find(Tree Node root,int min, int max){
if(root==null)
return max-min;
min=MATH.MIN(min,root. Val)
max =MATH.MAX (max, root. Val);
return MATH.MAX (find(root. Left,min,max),find(root. Right,min,max));
}
};
what's the point of naming a video in English, providing an English description, and beginning in English, only to suddenly switch to another language? thanks for wasting my time
Apologies for the inconvenience.
DONT KNOW HOW BUT I DID IT ON MY FIRST TRY IN O(N).
VERY HAPPY COZ OF IT :)
HERE IS MY CODE
class Solution {
public:
typedef pair P;
int ans;
P solve(TreeNode*root){
if(root == NULL){
return {INT_MAX,INT_MIN};//[-inf,inf]
}
P left = solve(root->left);
P right = solve(root->right);
int mini = min({root->val,left.first,right.first});
int maxi = max({root->val,left.second,right.second});
ans = max({ans,abs(root->val-mini),abs(root->val-maxi)});
return {mini,maxi};
}
int maxAncestorDiff(TreeNode* root) {
ans = 0;
solve(root);
return ans;
}
};