Initially, I was inclined to use BFS for this problem, based on my Intuition, but I was unsure about how to backtrack to the parent node. I had a vague idea but no concrete solution. However, after watching your explanation for just 7 minutes, it all made sense. I understood what I was missing and managed to write the code by myself. You are an exceptional storyteller. I admire your work immensely. It's evident that anyone who's been through your graph playlist could easily handle this question with just 4 to 7 minutes of your guidance.
Done in just 7 min yes sir improvement ho raha hai kaafi medium me aaj kal sab hi kar letaaa hu 8 out of 10.Thank u sir bas asa hi vedio create karte raho sir i sure ki contest me bhi achi rating hone wali hai jaldi hi.
Bhai mujhse problem nhi hote h medium wale 10 me se without help 3-4 hi approach kar pata gu rest of k liye mujhe video refer krna padta h please help me some suggestions please bhai
For anyone like me jo sochra hai unordered_set ke jagah vector use karne ka, toh in that case you will get TLE. The reason is due to the difference in time complexities of search operation for the 2 data structures. For set it's O(1) on average because internally it uses a hash table for storage whereas, for vector it is O(n) as we need to traverse each element to find the searched element. Now you can use searching techniques but that will make the code look more complex. PS 1: I'm very very new to graphs and I did not want to make my code look complex :) PS 2: Amazing explanation, coded entirely on my own (took a bit of reference for the queue thing as I was not using that inner while loop 🫠) after this explanation.
can we also traverse it by dfs and create a parent for each element and store in array for each node and while doing bfs we can just move to left, right and parent of node if not visited.
some space can be saved by making just the mapping for the parent, since we can already travel to the child here is the code class Solution { public: unordered_mapmp; TreeNode* makeMapping(TreeNode*root,int start){ queueq; q.push(root); TreeNode* begin = NULL; while(!q.empty()){ auto node = q.front(); q.pop(); if(node->val == start){ begin = node; } if(node->left){ mp[node->left] = node; q.push(node->left); } if(node->right){ mp[node->right] = node; q.push(node->right); } } return begin; } int solve(TreeNode* root, TreeNode* start){ queueq; q.push(start); unordered_setvisited; visited.insert(start); int time = 0; for(auto i:mp){ coutright) == 0){ visited.insert(node->right); q.push(node->right); } if(mp.count(node) > 0 && visited.count(mp[node]) == 0){ visited.insert(mp[node]); q.push(mp[node]); } } if(q.size() > 0){ time++; } } return time; } int amountOfTime(TreeNode* root, int start) { TreeNode*begin = makeMapping(root,start); return solve(root,begin); } };
sir aap ek baar ye code explain kr skte h ??? class Solution { public static TreeNode parent_link(TreeNode root,Mapmap,int start){ Queueq=new LinkedList(); TreeNode res=null; q.add(root); while(!q.isEmpty()){ TreeNode cur=q.poll(); if(cur.val==start) res=cur; if(cur.left!=null){ map.put(cur.left,cur); q.add(cur.left); } if(cur.right!=null){ map.put(cur.right,cur); q.add(cur.right); } } return res; } public int amountOfTime(TreeNode root, int start) { Mapparent_map=new HashMap(); TreeNode target=parent_link(root,parent_map,start);
Mapvisit=new HashMap(); Queuequ=new LinkedList(); visit.put(target,true); qu.add(target); int minTime=0; while(!qu.isEmpty()){ int size=qu.size(); int flag=0; for(int i=0;i
bhaiya can we do one thing , first we will find on which side their would be the infected node, after that we would calculate nodes from root to that infected node, now we would find height of visited node, then we would find height of the node to the other side of the root , add path from root+ infected root height +height on the other side to get the ans
bhaiya, i am solving the same question, getting "all testcases passed, but took too long" error. here's my code, instead of making it an undirected graph i just assigned parents to all nodes using unordered_map: class Solution { public: Solution(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } unordered_map ump; unordered_map vis; TreeNode* target; int amountOfTime(TreeNode* root, int start) { if(root==NULL){ return 0; } gen(root,start); vis[target]=1; queue q; q.push(target); int countmin = -1; while(!q.empty()){ countmin++; int size = q.size(); while(size--){ TreeNode* node = q.front(); q.pop(); if(node->left!=nullptr && vis[node->left]==0){ q.push(node->left); vis[node->left]=1; } if(node->right!=nullptr && vis[node->right]==0){ q.push(node->right); vis[node->right]=1; } if(node!=root && vis[ump[node]]==0){ q.push(ump[node]); vis[ump[node]]=1; } } } return countmin; } void gen(TreeNode* root, int start){ if(root == nullptr) return; if(root->val==start) target=root; vis[root]=0; if(root->left!=nullptr){ ump[root->left]=root; } gen(root->left,start); if(root->right!=nullptr){ ump[root->right]=root; } gen(root->right,start); } }; kya aap bata skte ho kyun ho raha hai aisa?
Maja aa Gaya bhai what a fabulous explanation ❤
best explanation on entire youtube
Initially, I was inclined to use BFS for this problem, based on my Intuition, but I was unsure about how to backtrack to the parent node. I had a vague idea but no concrete solution. However, after watching your explanation for just 7 minutes, it all made sense. I understood what I was missing and managed to write the code by myself. You are an exceptional storyteller. I admire your work immensely. It's evident that anyone who's been through your graph playlist could easily handle this question with just 4 to 7 minutes of your guidance.
Means a lot 🙏🙏❤️❤️
Done in just 7 min yes sir improvement ho raha hai kaafi medium me aaj kal sab hi kar letaaa hu 8 out of 10.Thank u sir bas asa hi vedio create karte raho sir i sure ki contest me bhi achi rating hone wali hai jaldi hi.
Bhai mujhse problem nhi hote h medium wale 10 me se without help 3-4 hi approach kar pata gu rest of k liye mujhe video refer krna padta h please help me some suggestions please bhai
The way use teaches makes it so easy to learn and intuitive to think, thanks a lot
Means a lot ❤️🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
My doubt cleared from this video. Thanks a lot mik
aapki voice bahut pyari hai 🥰
Great explanation 🔥
Keep uploading Bhaiya, you make me learn a lot 😄
Thank you.
Also watch the One Pass solution 😇
ua-cam.com/video/Xm8jIjAK_Zs/v-deo.htmlsi=JMM3MECQFApvF0vs
For anyone like me jo sochra hai unordered_set ke jagah vector use karne ka, toh in that case you will get TLE. The reason is due to the difference in time complexities of search operation for the 2 data structures. For set it's O(1) on average because internally it uses a hash table for storage whereas, for vector it is O(n) as we need to traverse each element to find the searched element.
Now you can use searching techniques but that will make the code look more complex.
PS 1: I'm very very new to graphs and I did not want to make my code look complex :)
PS 2: Amazing explanation, coded entirely on my own (took a bit of reference for the queue thing as I was not using that inner while loop 🫠) after this explanation.
Well explained.
Superb.
Waiting for one pass solution eagerly 😊
Really underrerated 😁😁😁😁
🙏🙏🙏
You made it so easy!
😇❤️🙏
best explanation bhai ,, thanks a lot
Most welcome 🙏
Guruji ❤❤❤
clean explanation 🔥
❤️🙏
Thanks 👍
hi, The time complexity for bfs is O(vertices + edges) can we apply the same here?
can we also traverse it by dfs and create a parent for each element and store in array for each node and while doing bfs we can just move to left, right and parent of node if not visited.
Yes that should work 👌👌
Thanks, bro i did it on my own Please make a video on the Biweekly contest Q4(2999 question)
THANKS!!
Please update this solution failing the last two test cases , time limit exceeded, use dp to optimise it😅
I stored node in hashmap but storing the values is the key
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
This approach is pretty staright forward , can you please explain the single pass dfs approach
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
it’s being uploaded now. Full intuitive explanation 😇❤️🙏
Bro just to inform that this code is giving a tle now when I run the same on lc. Pls check if possible why is it so?
same bro, did you manage to get through the TLE?
when will approach 2 come for this problem ???????????????????????????????????????????????????????
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
some space can be saved by making just the mapping for the parent, since we can already travel to the child
here is the code
class Solution {
public:
unordered_mapmp;
TreeNode* makeMapping(TreeNode*root,int start){
queueq;
q.push(root);
TreeNode* begin = NULL;
while(!q.empty()){
auto node = q.front();
q.pop();
if(node->val == start){
begin = node;
}
if(node->left){
mp[node->left] = node;
q.push(node->left);
}
if(node->right){
mp[node->right] = node;
q.push(node->right);
}
}
return begin;
}
int solve(TreeNode* root, TreeNode* start){
queueq;
q.push(start);
unordered_setvisited;
visited.insert(start);
int time = 0;
for(auto i:mp){
coutright) == 0){
visited.insert(node->right);
q.push(node->right);
}
if(mp.count(node) > 0 && visited.count(mp[node]) == 0){
visited.insert(mp[node]);
q.push(mp[node]);
}
}
if(q.size() > 0){
time++;
}
}
return time;
}
int amountOfTime(TreeNode* root, int start) {
TreeNode*begin = makeMapping(root,start);
return solve(root,begin);
}
};
Nice ❤️🙏
Thank you bhaiya waiting for single traversal approach :)
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
@@codestorywithMIK thank you bro🙏🙏. I am currently searching for internship but can't find anywhere 😔 feels depressing, meantime I am gonna skill up
i used for(int i=0;i
Can you please share full code.
please make video of one time traversal for this problem
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
I used stack, although recursion is stack
stack st;
st.push(root);
while(!st.empty()){
auto node = st.top();
st.pop();
if(node->right){
int parent = node->val;
int child = node->right->val;
adj[parent].push_back(child);
adj[child].push_back(parent);
st.push(node->right);
}
if(node->left){
int parent = node->val;
int child = node->left->val;
adj[parent].push_back(child);
adj[child].push_back(parent);
st.push(node->left);
}
}
Java plz bhaiya ❤
Hi there, JAVA code is available in the GitHub link in the description. Will that help ? ❤️
Bhai nayi wali video jo iska 2nd part hai jaldi dalo bhai!!!!
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
❤
please upload one pass solution
Yes it’s being uploaded now. Full intuitive explanation 😇❤️🙏
sir aap ek baar ye code explain kr skte h ???
class Solution {
public static TreeNode parent_link(TreeNode root,Mapmap,int start){
Queueq=new LinkedList();
TreeNode res=null;
q.add(root);
while(!q.isEmpty()){
TreeNode cur=q.poll();
if(cur.val==start) res=cur;
if(cur.left!=null){
map.put(cur.left,cur);
q.add(cur.left);
}
if(cur.right!=null){
map.put(cur.right,cur);
q.add(cur.right);
}
}
return res;
}
public int amountOfTime(TreeNode root, int start) {
Mapparent_map=new HashMap();
TreeNode target=parent_link(root,parent_map,start);
Mapvisit=new HashMap();
Queuequ=new LinkedList();
visit.put(target,true);
qu.add(target);
int minTime=0;
while(!qu.isEmpty()){
int size=qu.size();
int flag=0;
for(int i=0;i
class Solution {
private Mapadj=new HashMap();
public int amountOfTime(TreeNode root,int start){
convertToGraph(root);
Dequeq=new ArrayDeque();
Setvis=new HashSet();
q.offer(start);
int time=-1;
while(!q.isEmpty()){
time++;
for(int sz=q.size();sz>0;sz--){
int curNode =q.pollFirst();
vis.add(curNode);
if(adj.containsKey(curNode)){
for(int it:adj.get(curNode)){
if(!vis.contains(it))
q.offer(it);
}
}
}
}
return time;
}
private void convertToGraph(TreeNode root){
if(root==null) return;
if(root.left!=null){
adj.computeIfAbsent(root.val,k->new ArrayList()).add(root.left.val);
adj.computeIfAbsent(root.left.val,k->new ArrayList()).add(root.val);
}
if(root.right!=null){
adj.computeIfAbsent(root.val,k->new ArrayList().add(root.right.val);
adj.computeIfAbsent(root.right.val,k->new ArrayList()).add(root.val);
adj.computeIfAbsent( root.right.val,k->new ArrayList()).add(root.val);
}
convertToGraph(root.left);
convertToGraph(root.right);
}
}
dfs apporach.
class Solution {
private int maxDist=0;
public int amountOfTime(TreeNode root,int start){
dfs(root,start);
return maxDist;
}
public int dfs(TreeNode root,int start){
int depth=0;
if(root==null) return depth;
int leftDepth=dfs(root.left,start);
int rightDepth=dfs(root.right,start);
if(root.val==start){
maxDist =Math.max(leftDepth,rightDepth);
depth=-1;
}else if(leftDepth>=0&&rightDepth>=0){
depth=Math.max(leftDepth,rightDepth)+1:
}else{
int dist=Math.abs(leftDepth)+Math.abs(rightDepth);
maxDist=Math.max(maxDist,dist);
depth =Math.min(leftDepth,rightDepth)-1;
}
return depth;
}
}
🎉😂❤
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
bhaiya can we do one thing , first we will find on which side their would be the infected node, after that we would calculate nodes from root to that infected node, now we would find height of visited node, then we would find height of the node to the other side of the root , add path from root+ infected root height +height on the other side to get the ans
bhaiya, i am solving the same question, getting "all testcases passed, but took too long" error. here's my code, instead of making it an undirected graph i just assigned parents to all nodes using unordered_map:
class Solution {
public:
Solution(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
unordered_map ump;
unordered_map vis;
TreeNode* target;
int amountOfTime(TreeNode* root, int start) {
if(root==NULL){
return 0;
}
gen(root,start);
vis[target]=1;
queue q;
q.push(target);
int countmin = -1;
while(!q.empty()){
countmin++;
int size = q.size();
while(size--){
TreeNode* node = q.front();
q.pop();
if(node->left!=nullptr && vis[node->left]==0){
q.push(node->left);
vis[node->left]=1;
}
if(node->right!=nullptr && vis[node->right]==0){
q.push(node->right);
vis[node->right]=1;
}
if(node!=root && vis[ump[node]]==0){
q.push(ump[node]);
vis[ump[node]]=1;
}
}
}
return countmin;
}
void gen(TreeNode* root, int start){
if(root == nullptr) return;
if(root->val==start) target=root;
vis[root]=0;
if(root->left!=nullptr){
ump[root->left]=root;
}
gen(root->left,start);
if(root->right!=nullptr){
ump[root->right]=root;
}
gen(root->right,start);
}
};
kya aap bata skte ho kyun ho raha hai aisa?
The way use teaches makes it so easy to learn and intuitive to think, thanks a lot
❤