Це відео не доступне.
Перепрошуємо.
L51. Two Sum In BST | Check if there exists a pair with Sum K
Вставка
- Опубліковано 19 сер 2024
- Entire DSA Course: takeuforward.o...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/take...
#treeSeries #striver #placements
Words aren't enough to explain how grateful we are to learn from you and that too for free. Thankyou so much Striver! :)
Thank you for your effort Striver, you are making a difference.
Is that morse code?
He made the difference bro now its our turn
@@parthsalat what do you mean? Please clarify
Searched across whole UA-cam but no one has taught this method. ThankYou Striver! :)
bhiya, aap kaa coding style bohot neat, clear hai. Bohot awesome code karte ho aap, pata nhi mai kab apne se aise code kar paungi...
I would say, this is an amazing approach!
Thank you so much Striver, Your Tree Series has helped a lot!
The way you explain the intution was excellent sir. The code quality is also awesome sir. You are helping a lot of students sir. Thanks from the bottom of my heart.
Brilliant analogy drawn from the BST iterator probelm
This was so intuitive , learnt a lot. huge thanks man !
Wow!!! Never seen anyone explain something with this ease!!!
Amazing way to use 2 pointers approach in BST. Thanks alot👍
Efforts you put while explaining is just hats off !
Thankyou Striver !
This explanation and quality of code was exceptional, thanks a lot striver
Just blew my mind...! Best explanation...Thank you for the series
this vedio helped me to reduce classes for my code for building an atm machine using classes code in an interview thank you so much striver .....
If there can be equal values in the BST, we can return the TreeNode pointer instead of returning its value. Then, we just check if left==high pointer in while loop.
Amazing ! just grateful for this kind of content
we can use SET while traversing in inorder, so timecomplexity==N, space complexity==N i.e N < 2*H
same thought but in most cases Space complexity O(N > 2H) will be there
Another way of doing it by using and unordered_Set
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_set set;
return dfs(root,k,set);
}
bool dfs(TreeNode* root , int k , unordered_set&set){
if(!root) return false;
if(set.count(k-root->val))return true;
set.insert(root->val);
return dfs(root->left,k,set) || dfs(root->right,k,set);
}
};
this is amazing thank you striver you're truly a role model
this is even similar like two sum problems
visit=set()
q=[root]
for i in q:
if (k-i.val) in visit:return True
visit.add(i.val)
if i.left:
q.append((i.left))
if i.right:
q.append(i.right)
return False
Dada please tell when we are going to get the free ka Dp Series..... Any estimate date??
btw this tree series is truly helpful for me.
thankyou @striver for providing this quality content for free.You are doing the great job and i hope we will be finding such premium content from your side.
Understood.
Thank you Bhaiya for this awesome Series :)
Class solution { Hash seths=new hash set();
Public boolean find Target (Treenode root,int k,){
If(root ==null)return false;
If(hs.contain(root. Val)return true;
Hs.add(k-root.val);
Find Target (root. right,k)||find Target (root. left,k)
tum yha par bhi
Yrr mind blown man, highest respect to your series man!
This code demonstrates why we should use class 🗿🧐
Fantastic problem and Fantastic explanation !!
Thank You So Much Striver Brother...🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
this was a very creative approach.
we cannot do l.hasNext()!=NULL && r.hasNext()!=NULL instead of i
Same query
Just follow the same two pointer approach as used in the array, but in tree😀
class Solution {
public:
struct Pair{
TreeNode* node;
int state;
Pair(TreeNode *node, int state){
this->node = node;
this->state = state;
}
};
TreeNode* getNextInorderFromNormalStack(stack &ls){
while(!ls.empty()){
Pair tp = ls.top();
if(tp.state == 0){
ls.top().state++;
if(tp.node->left) {
Pair p = Pair(tp.node->left, 0);
ls.push(p);
}
} else if(tp.state == 1){
ls.top().state++;
TreeNode* n = tp.node;
if(tp.node->right) {
Pair p = Pair(tp.node->right, 0);
ls.push(p);
}
return n;
} else if(tp.state == 2){
ls.pop();
}
}
return nullptr;
}
TreeNode* getNextInorderFromReverseStack(stack &rs){
while(!rs.empty()){
Pair tp = rs.top();
if(tp.state == 0){
rs.top().state++;
if(tp.node->right) {
Pair p = Pair(tp.node->right, 0);
rs.push(p);
}
} else if(tp.state == 1){
rs.top().state++;
TreeNode* n = tp.node;
if(tp.node->left) {
Pair p = Pair(tp.node->left, 0);
rs.push(p);
}
return n;
} else if(tp.state == 2){
rs.pop();
}
}
return nullptr;
}
bool findTarget(TreeNode* root, int k) {
stack ls;
stack rs;
ls.push({root, 0});
rs.push({root, 0});
TreeNode* left = getNextInorderFromNormalStack(ls);
TreeNode* right = getNextInorderFromReverseStack(rs);
while(left->val < right->val){
if(left->val + right->val < k){
left = getNextInorderFromNormalStack(ls);
} else if(left->val + right->val > k){
right = getNextInorderFromReverseStack(rs);
} else {
return true;
}
}
return false;
}
};
love it man ;)
thank you striver for your entire efforts...thanks alot
Nobody taught this approach except you! GOAT
class Solution {
List ls = new ArrayList();
public boolean findTarget(TreeNode root, int k) {
if(root == null) return false;
if(ls.contains(k-root.val)) return true;
ls.add(root.val);
return findTarget(root.left, k) || findTarget(root.right, k);
}
}
Understood. Wonderful Explanation !!
@8:07
best expressions
Understood.
Thank you Bhaiya for all your efforts.
Just do an inorder traversal and store it and then just check if there are any two numbers whose sum is ==k using the array
Hey dude, for the first approach i.e. storing the elements in an array, is taking 2 ms time and 41.1 MB space, and BST iterator technique is taking 8 ms and 47.5 MB space in leetcode, probably the delay is caused because creating a seprarate class and calling the methods is taking more time.
don't focus on leetcode time and space they are not accurate
here you are using stack and in the worst case it will also take O(N) space complexity.
Great Explanation
"value badhana hoga"
Will it work for skew trees??
God level explanation for sure!! DAMN!!! Thank you so much!!!
wow, this was a fantastic solution using the iterator..
Appreciate ur series. 🔥💯
What an explanation
Hats off to u
Brilliant code man, too good!
HI Striver, could you please update the SDE sheet with missing links for code and youtube video link, Many of us are following it for our preparation.
You'll need to press the youtube thanks button for that
Thanks for video best video 💝🎁
We can also use a Dequeue in Java
In c++ also
EASY APPROACH :)
class Solution{
public:
int isPairPresent(struct Node *root, int target)
{
vector nums;
inorder(root,nums);
return findTarget(nums,target);
}
private : void inorder(struct Node* node, vector& nums)
{
if (!node) return;
inorder(node->left, nums);
nums.push_back(node->data);
inorder(node->right, nums);
}
bool findTarget(vector a, int target)
{
for (int i = 0, j = a.size() - 1; i < j;)
{
int sum = a[i] + a[j];
if (sum == target) return true;
else if (sum < target) i++;
else j--;
}
return false;
}
};
He already told this approach in the starting of this video ,it s about improving space complexity
thanks a lot for yr help and support...
if we are aloowed to change the data or a tree , we can just fallten these trees and make a doubly linked list from it . , now our taskl is now converted to simply traverse a DLL.
This cannot get more simple.
👌👌 great explanation
WOW! This is pure Gold!!!
Thanks so much Striver!!!!!!!!
Can you please make a python code too ? If possible ofcourse ...It will be really helpful
can we use flattening BST to doubly Linked List and then apply 2 pointer as it would also take O(N) time and O(H) space
You are modifying the tree. Interviewer will not be happy !!
Easiest Approach, Just amazing
omg omg, absolutely speechless never seen such type of code before,learned a lot.
Can the problem be solved in this way? If we iterate over each node 'n', and search for (k - n->val). It takes O(nlogn) time and O(1) space.
haa but yeh to costly hogya na , suppose your tree is a skewed tree so rather than O(nlogn) , you would end up taking O(n*n) solution
why did we need to create objects , why cant we use BSTiterator as function?
really awesome!
Please make a video on printing all paths from root to leaves
Objects idea is ellite
Wow , what a fantastic explanation , u explained and I coded it myself
My Coding style is a bit different but my solution got accepted in Leetcode
My Code :
class BSTIterator{
public:
stack st;
BSTIterator(TreeNode *root, int flag){
if (flag == 1){
while (root != NULL){
st.push(root);
root = root->right;
}
}
else {
while (root != NULL){
st.push(root);
root = root->left;
}
}
}
int next(){
TreeNode *currNode = st.top();
st.pop();
if (currNode->right != NULL){
TreeNode *temp = currNode->right;
while (temp != NULL){
st.push(temp);
temp = temp->left;
}
}
return currNode->val;
}
int before(){
TreeNode *currNode = st.top();
st.pop();
if (currNode->left != NULL){
TreeNode *temp = currNode->left;
while (temp != NULL){
st.push(temp);
temp = temp->right;
}
}
return currNode->val;
}
};
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
if (root == NULL) return false;
BSTIterator l(root, 0); //next
BSTIterator r(root, 1); //before
int i = l.next();
int j = r.before();
while (i < j){
if (i + j == k) return true;
else if (i + j < k) i = l.next();
else j = r.before();
}
return false;
}
};
striver se better tera code lag rha
@@atifhu thanks for the compliment ❤️ , but Striver is God
class Solution {
public:
stack largest;
stack smallest;
void leftiterator(TreeNode* root, stack &smallest){
while(root){
smallest.push(root);
root=root->left;
}
}
void rightiterator(TreeNode* root, stack &largest){
while(root){
largest.push(root);
root=root->right;
}
}
bool findTarget(TreeNode* root, int k) {
leftiterator(root, smallest);
rightiterator(root, largest);
while(largest.top()!=smallest.top())
{if(smallest.top()->val+largest.top()->val==k)
return true;
if(smallest.top()->val+largest.top()->val>k){
TreeNode* x= largest.top();
largest.pop();
rightiterator(x->left, largest);
}
else{
TreeNode* x= smallest.top();
smallest.pop();
leftiterator(x->right, smallest);
}}
return false;
}
};
I coded exact same code using 2 stacks
Thank you sir
why is while(i < j ) working ? since i and j will be values and not index ?
I suppose, because I initially points to the very smallest value and j points to the very largest value. When I crosses j, it means that it has crossed all of the values that could add up to the answer.
BST property, all left are smaller than right
can we convert this bst into dbll and then 2 pointer ?
Yeah
damm, how could i think that if i have not seen the solution, i only thought for O(n) and O(n)
Thank you Bhaiya
1st approach:
public class Solution {
public bool FindTarget(TreeNode root, int k) {
List inorder = new List();
Inorder(root, inorder);
int i=0, j=inorder.Count-1;
while(j>i){
if(inorder[i]+inorder[j]>k){
j--;
}
if(inorder[i]+inorder[j]i){
i++;
}
if(inorder[i]+inorder[j]==k&& j>i){
return true;
}
}
return false;
}
public static void Inorder(TreeNode root, List inorder){
if(root==null){
return;
}
Inorder(root.left, inorder);
inorder.Add(root.val);
Inorder(root.right, inorder);
}
}
Thank you, Striver!!!
is this last video of the series
Thankx for this valuable series
i am little confuse how we can do next() and before() in just one stack?
We are creating two different object of the same class.
This algorithm - What a beauty! 😍
doing by the help of vector and 2 pointers is wrong?
Its not wrong but using BST iterator is the most optimized solution for this problem as it uses space complexity of O(H).
that has space complexity of O(n) while optimized version has O(logN)
Thanks Raj for the Tree series.
If we have two trees and we need to count the total no of pairs whose sum is X and pair should be form using one node from one tree and another node from another?
bhaiya ap hindi bhi bola karo bich bich me
bhaut achha lagta haii
Brilliant solution
understood
Ty
Also recursive solution:
class Solution {
public:
bool finding(TreeNode* root, int k){
if(root==NULL) return false;
if(root->val == k) return true;
if(k < root->val) return finding(root->left, k);
if(k > root->val) return finding(root->right, k);
return false;
}
bool check(TreeNode* temp, TreeNode* root, int k){
if(root==NULL) return false;
// if(root->val == k) return true; -> causing error in 3rd TC
int rem = k - root->val;
if(rem!=root->val and finding(temp, rem)) return true;
if(check(temp, root->left, k) or check(temp, root->right, k)) return true;
return false;
}
bool findTarget(TreeNode* root, int k) {
if(root==NULL) return false;
return check(root, root, k);
}
};
lovely, sir love u a lot, sir learning a lot from your lecture
awesome literally just awesome
Bhaiya why space is O(h) why not O(n) we are storing all the nodes of BST in Stcak right ?
No, we are not. At any point in time, only the O(H) nodes can be present in the stack.
Please do a dry run and check if your stack overflows the height of your tree
we love your content and we love you...🖤
TYSM Brother!!!
How are we ensuring that we do not consider the same element twice?
Understood thanks :)
understood. thanks.
understood.
Woooooooow Amazing explaination 😍😍
sira approach
kaint approach
Will it work for tree with 1, 2,3,4,5 because first we willtake (5,4,3,2,1) then (5 ) for other . when we want sum as 7 we do like . 1+5 ans then 2+5 its ok in that case stack modifies as (5,4,3) and (4,3,2,1) casue 5 pops out. then check again (4+5) > 7 pop out from 2nd stack (5,4,3) and (3,2,1) and again (5+3>7) pop out from 2nd (5,4,3) and (2,1) we only pop from 2nd stack not the one with max right . in that case again (5+2) again 7 same result. so we pop both . (4,3) and (1) . we are missing one more case of 4+3 right in this ?