sir i dont know why you are so underrated? bhut sare teachers se pdha hun me unka content itna accha bhi nhi hota phir bhi bhaut acche viwes or aap itna bahdiya samjhate ho phirv bhi itne kam views
This means a lot to me that you mentioned this. I usually don’t show face or promote it everywhere, may be that is the reason. But I hope someday people will get to know about the channel. Hope the day comes soon ❤️🙏😇 Thank you again ❤️🙏
@@codestorywithMIK You must promote it everywhere sir. You are literally the best. I always share your channel to almost anyone I know. I will be there to witness you reaching 1 Million soon.
I tried understanding from other channels and leetcode editorial, but couldn't. Only after seeing your two videos today, I finally understood. Your code is so clean and the breakdown is so good. In the end, it all boiled down to the BFS implementation.
Your previous video on Diameter finding helped me a lot to build the concept on this topic , was able to solve this one own, AC in first submit . much appreciated !
Amazing explaination Sir !!! I made a very good decision not wactching today's POTD video of any other creater. The efforts you have made for explaining this question is really appreciable.
They say when you don't have something only then you understand its worth I realized in the 2-3 days you did'nt post video because I tried to study with other creators but did'nt get the hang of things and then I missed your videos so much. And the way you teach things it makes you want to study and solve problems
class Solution { public: pair bfsTofindFarthestNode(int s, int v, unordered_map& adj) { vector vis(v, false); queue q; q.push(s); vis[s] = true; // Mark starting node as visited int level = 0, farthestNode = s; while (!q.empty()) { int n = q.size(); for (int i = 0; i < n; i++) { int node = q.front(); q.pop(); farthestNode = node; for (auto it : adj[node]) { if (!vis[it]) { vis[it] = true; // Mark neighbor as visited before enqueueing q.push(it); } } } if (!q.empty()) level++; } return {farthestNode, level}; } int treeDiameter(vector& edges) { int v = edges.size() + 1; // Number of nodes unordered_map adj; for (const auto& edge : edges) { int u = edge[0], v = edge[1]; adj[u].push_back(v); adj[v].push_back(u); } auto oneEndNode = bfsTofindFarthestNode(0, v, adj); auto otherEndNode = bfsTofindFarthestNode(oneEndNode.first, v, adj); return otherEndNode.second; // Diameter of the tree } int minimumDiameterAfterMerge(vector& edges1, vector& edges2) { int dia1 = treeDiameter(edges1); int dia2 = treeDiameter(edges2); int combinedDia = ceil(dia1 / 2.0) + ceil(dia2 / 2.0) + 1; return max({dia1, dia2, combinedDia}); } };
@codestorywithMIK, My first thought was of using tropological sort, but couldn't figure out how that can be used to calculate the diameter. Read the tutorial but cannot clearly understand. Can you please make one more video solving this problem using tropological sort?
Hello sir. Thanks for a wonderful explanation on this tree diameter concept. Recently a question came in LC contest on 1st Dec. In that question also two undirected trees are given and we have to join them. The concept is similar to this question but still facing a problem in understanding the solution. Here is the problem: LC 3372(Maximize the Number of Target Nodes After Connecting Trees I ). Will it be possible for u to make a video on this particular question. Thanks again.
Bhaiya aap ye sat aur sunday ka jo potd tha uska video explanation bana sakte ho kyunki vo streak maintain rakhne ke liye code ek jagah se solve to kar liya par explanation aapke jesa nai tha to aap kya vo do problems ke video bana sakte ho? It will be very helpful for us🙏🏻
Hi bhaiya, really nice explanation of both the problems, but I got confused in one thing. In the problem why they have used word 'minimum diameter' as we are just focusing on finding the maximum diameter after merging the trees. Could you please explain
Hi Anand, Remember that the definition of Diameter is the longest path between any two nodes. We anyways have to return the longest path but the only way we can shorten the diameter is by connecting them in the mid of diameters of each of them. Even after connecting them from mid, we have to return the Diameter (longest path between two nodes in the connected trees). The minimum word used in the problem statement is just to let us know that there is a chance to minimise it if the trees are connected in the mid
I have one doubt Sir... If i am not able to solve a hard question should i jump to the solution after 30-40 mins or should i try solving it so that my analytical and problem solving skills improve no matter how many days it takes
i have solved dfs. public int minimumDiameterAfterMerge(int[][]edges1,int[][]edges2){ int d1=findDiameter(edges1); d2=findDiameter(edges2); return Math.max(Math.max(d1-1,d2-1),d1/2+d2/2+1); } private int findDiameter(int[][]edges){ Listadj=new ArrayList(); for(int i=0;i
Diameter is actually the longest path of within a graph/tree between any two nodes. If you choose the minimum of the three, then you won't be actually choosing the diameter. The only way to minimise the diameter of the combined tree is by combining them at the middle of the diameters. Notice he stressed in this part at 14:44
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day
because the graph is undirected , we can visit one node twice , 1-2-3 , if you go to 2 , you are gonna get two nodes connected , 1 and 3 , and if you are coming from 1 , you have already visited it, that may go enless in loop
sir i dont know why you are so underrated? bhut sare teachers se pdha hun me unka content itna accha bhi nhi hota phir bhi bhaut acche viwes or aap itna bahdiya samjhate ho phirv bhi itne kam views
This means a lot to me that you mentioned this. I usually don’t show face or promote it everywhere, may be that is the reason. But I hope someday people will get to know about the channel.
Hope the day comes soon ❤️🙏😇
Thank you again ❤️🙏
@@codestorywithMIK you should start promoting bhai... acchi cheeze and acche log aage aane chaiye... they should lead... love you bhai :)
@@codestorywithMIK You must promote it everywhere sir. You are literally the best.
I always share your channel to almost anyone I know. I will be there to witness you reaching 1 Million soon.
@@codestorywithMIK yes sir in my view you are the best for dsa just like hitesh choudhary sir for dev in india.
Best teacher of all time for DSA. i feel very good that i am having u as my teacher ❤
a true teacher doesn't only teach but also provides development you are a perfect example sir
I tried understanding from other channels and leetcode editorial, but couldn't. Only after seeing your two videos today, I finally understood. Your code is so clean and the breakdown is so good. In the end, it all boiled down to the BFS implementation.
same bro
❤️🙏
This question and explanation are way too much awesome. Got to Learn a lot from this video and the last video :)
Hats off ❤❤❤❤Thank you man
one word - LEGEND ❤
Thanks a lot!
learned a very useful concept from this ques, thank to you!
Best DSA youtuber bhai!
You are legend bro, they way you approach the problem. For me you are the greatest motivation.
This means a lot to me 🙏❤️
Thankss SIR!!
You made this question easy from prev 44 no video, this video is literally a cake walk
Your previous video on Diameter finding helped me a lot to build the concept on this topic , was able to solve this one own, AC in first submit . much appreciated !
Amazing explaination Sir !!!
I made a very good decision not wactching today's POTD video of any other creater. The efforts you have made for explaining this question is really appreciable.
Thank you for your kind words and support. 🙏
@@codestorywithMIK Sir can you also give some guidence on, how to approach any problem, how to find patterns among different questions ?
Thanks
Video-44 Link : th-cam.com/video/na3LE8CBYLo/w-d-xo.html
watched the video no 44 then solved today's potd by myself thankyou itna acha explanation ke liye...♥♥
They say when you don't have something only then you understand its worth I realized in the 2-3 days you did'nt post video because I tried to study with other creators but did'nt get the hang of things and then I missed your videos so much. And the way you teach things it makes you want to study and solve problems
Thank you for your kind words ❤️🙏
class Solution {
public:
pair bfsTofindFarthestNode(int s, int v, unordered_map& adj) {
vector vis(v, false);
queue q;
q.push(s);
vis[s] = true; // Mark starting node as visited
int level = 0, farthestNode = s;
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
int node = q.front();
q.pop();
farthestNode = node;
for (auto it : adj[node]) {
if (!vis[it]) {
vis[it] = true; // Mark neighbor as visited before enqueueing
q.push(it);
}
}
}
if (!q.empty()) level++;
}
return {farthestNode, level};
}
int treeDiameter(vector& edges) {
int v = edges.size() + 1; // Number of nodes
unordered_map adj;
for (const auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
auto oneEndNode = bfsTofindFarthestNode(0, v, adj);
auto otherEndNode = bfsTofindFarthestNode(oneEndNode.first, v, adj);
return otherEndNode.second; // Diameter of the tree
}
int minimumDiameterAfterMerge(vector& edges1, vector& edges2) {
int dia1 = treeDiameter(edges1);
int dia2 = treeDiameter(edges2);
int combinedDia = ceil(dia1 / 2.0) + ceil(dia2 / 2.0) + 1;
return max({dia1, dia2, combinedDia});
}
};
First 🎉❤
thanks for the amazing explanation. will you be making videos for the questions which were missed?
Pls post a video for 2940 leetcode problem which was day before yesterdays potd of leetcode
Make video on Sunday hard with and without segment trees
bhaiya pls solve sunday's potd
@codestorywithMIK, My first thought was of using tropological sort, but couldn't figure out how that can be used to calculate the diameter. Read the tutorial but cannot clearly understand. Can you please make one more video solving this problem using tropological sort?
Hello sir. Thanks for a wonderful explanation on this tree diameter concept. Recently a question came in LC contest on 1st Dec. In that question also two undirected trees are given and we have to join them. The concept is similar to this question but still facing a problem in understanding the solution. Here is the problem: LC 3372(Maximize the Number of Target Nodes After Connecting Trees I ). Will it be possible for u to make a video on this particular question. Thanks again.
Please release your course
Sir wo Daily challenge ek miss ho gya to wo bhe bna do please smjh nhi aa rha hai.
2940. Find Building Where Alice and Bob Can Meet
Please sir release your course bhaiya
Bhaiya aap ye sat aur sunday ka jo potd tha uska video explanation bana sakte ho kyunki vo streak maintain rakhne ke liye code ek jagah se solve to kar liya par explanation aapke jesa nai tha to aap kya vo do problems ke video bana sakte ho?
It will be very helpful for us🙏🏻
Hi bhaiya, really nice explanation of both the problems, but I got confused in one thing. In the problem why they have used word 'minimum diameter' as we are just focusing on finding the maximum diameter after merging the trees. Could you please explain
Hi Anand,
Remember that the definition of Diameter is the longest path between any two nodes.
We anyways have to return the longest path but the only way we can shorten the diameter is by connecting them in the mid of diameters of each of them.
Even after connecting them from mid, we have to return the Diameter (longest path between two nodes in the connected trees).
The minimum word used in the problem statement is just to let us know that there is a chance to minimise it if the trees are connected in the mid
@@codestorywithMIK thank you for explaining bhaiya
That means bhaiya I need all minimum diameter from the graph, and then return maximum one
Op Op op
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day @codestorywithMIK
Time complexity of this algo??
Java Code
class Solution {
public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
Map adj1 = buildAdj(edges1);
Map adj2 = buildAdj(edges2);
int diameter1 = findDiameter(adj1);
int diameter2 = findDiameter(adj2);
// +1 for edge which is joining G1 and G2
int combined = ((diameter1 + 1) / 2) + ((diameter2 + 1) / 2) + 1;
return Math.max(Math.max(diameter1, diameter2), combined);
}
private Map buildAdj(int[][] edges) {
Map adj = new HashMap();
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
// Add v to u's adjacency list
adj.putIfAbsent(u, new ArrayList());
adj.get(u).add(v);
// Add u to v's adjacency list
adj.putIfAbsent(v, new ArrayList());
adj.get(v).add(u);
}
return adj;
}
private int findDiameter(Map adj) {
if (adj.isEmpty())
return 0;
Pair pair1 = bfs(adj, 0); // 0 is my random node
Pair pair2 = bfs(adj, pair1.nodeVal);
return pair2.distance; // this is diameter
}
private Pair bfs(Map adj, int source) {
Queue q = new LinkedList();
boolean[] visited = new boolean[adj.size()];
q.offer(source);
visited[source] = true;
Integer fatherstNode = source;
Integer distance = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Integer node = q.poll();
fatherstNode = node;
if (adj.get(node) != null) {
for (Integer nbr : adj.get(node)) {
if (!visited[nbr]) {
visited[nbr] = true;
q.offer(nbr);
}
}
}
}
if (!q.isEmpty()) {
distance++;
}
}
return new Pair(fatherstNode, distance);
}
}
class Pair {
int nodeVal;
int distance;
public Pair(int nodeVal, int distance) {
this.nodeVal = nodeVal;
this.distance = distance;
}
}
Hello MIK sir, can you tell me why leetcode mention tree, when they actually gave graph. 🤔
I have one doubt Sir... If i am not able to solve a hard question should i jump to the solution after 30-40 mins or should i try solving it so that my analytical and problem solving skills improve no matter how many days it takes
Don’t spend more than an hour.
Then try to see what is missing in your understanding, take hint and then try again.
i have solved dfs.
public int minimumDiameterAfterMerge(int[][]edges1,int[][]edges2){
int d1=findDiameter(edges1);
d2=findDiameter(edges2);
return Math.max(Math.max(d1-1,d2-1),d1/2+d2/2+1);
}
private int findDiameter(int[][]edges){
Listadj=new ArrayList();
for(int i=0;i
I didnt get this there it is memtioned minimum diameter but we are sending max
Diameter is actually the longest path of within a graph/tree between any two nodes. If you choose the minimum of the three, then you won't be actually choosing the diameter. The only way to minimise the diameter of the combined tree is by combining them at the middle of the diameters. Notice he stressed in this part at 14:44
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day
While bfs why we are checking visited here because we haven't checked this thing while doing any other question but why here
because the graph is undirected , we can visit one node twice , 1-2-3 , if you go to 2 , you are gonna get two nodes connected , 1 and 3 , and if you are coming from 1 , you have already visited it, that may go enless in loop
@annagarg2567 oh thanks